Tight bounds for gap-labellings

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

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]-vertexlabelling) of a graph. In this work, we study the edge-gap number, χgE , and the vertexgap number, χgV , of cycles, crowns and wheels.