| Texto completo | |
| Autor(es): |
Weffort-Santos, Celso A.
;
Schouery, Rafael C. S.
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | DISCRETE APPLIED MATHEMATICS; v. 339, p. 19-pg., 2023-11-15. |
| Resumo | |
A gap -[k] -vertex-labelling of a graph G is a pair (& pi;, c & pi;), where & pi; : V (G) [k] and c & pi; : V (G) {0, 1, ... , k} is a proper colouring of G such that, for v & ISIN; V (G), c & pi;(v) = max {& pi;(u)} - min {& pi;(u)}, if d(v) > 2, and c & pi;(v) = & pi;(u)u & ISIN;N(v), otherwise. In u & ISIN;N(v) u & ISIN;N(v) this paper, we present an upper bound of O(n2) for the vertex-gap number of arbitrary graphs, which is the least number k such that G admits a gap -[k]-vertex-labelling. We prove that, for n > 4, Kn does not admit any gap-vertex-labelling, regardless of the number of labels. We also characterize the powers of cycles and paths that admit gapvertex-labellings. Furthermore, we introduce a novel parameter, the gap-strength of a graph, denoted by strgap(G), which is the least number of edges that must be removed from a graph, so it will have a gap-vertex-labelling, and prove that strgap(Kn) & ISIN; & OHM;(n6/5) and strgap(Kn) & ISIN; O(n3/2).& COPY; 2023 Elsevier B.V. All rights reserved. (AU) | |
| Processo FAPESP: | 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural |
| Beneficiário: | Flávio Keidi Miyazawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |