Tight bounds for gap-labellings

• C. A. Weffort-Santos UNICAMP
• C. N. Campos UNICAMP
• R. C. S. Schouery UNICAMP

DOI: https://doi.org/10.5753/etc.2017.3194

Resumo

An ordered pair (π, c_π) is said to be a gap-[k]-edge-labelling (gap-[k]-vertex-labelling) if π is an edge-labelling (vertex-labelling) on the set {1, . . . , k}, and c_π is a proper vertex-colouring induced by a gap-function based on π. Gap-[k]-edge-labellings and gap-[k]-vertex-labellings were first introduced by M. Tahraoui et al. [7] and A. Dehghan et al. [2], respectively. The edge-gap number (vertex-gap number) is the least k for which there exists a gap-[k]-edge-labelling (gap-[k]-vertex-labelling) of a graph. In this work, we study the edge-gap number, χ^g_E, and the vertex-gap number, χ^g_V, of cycles, crowns and wheels.

Referências

A. Brandt, B. Moran, K. Nepal, F. Pfender, D. Sigler, Local gap coloring from edge labelings, Australasian Journal of Combinatorics 65(3) (2016), 200-211.

A. Dehghan, M.-R. Sadeghi and A. Ahad, Algorithmic complexity of proper labeling problems, Theoretical Computer Science 495 (2013), 25 - 36.

J. A. Gallian, A dynamic survey of graph labeling, The Electronic Journal of Combinatorics DS6 (2016)

A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (International Symposium) (1967), 394-355.

R. Scheidweiler, E. Triesch, New estimates for the gap chromatic number, SIAM Journal of Discrete Mathematics 328 (2014), 42-53.

R. Scheidweiler, E. Triesch, Gap-neighbour-distinguishing colourings, Journal of Combinatorial Mathematics and Combinatorial Computing, 94 (2015), 205-214.

M. A. Tahraoui, E. Duchene, H. Kheddouci, Gap vertex-distinguishing edge colourings of graphs, Discrete Mathematics 312 (20) (2012), 3011 - 3025.