On gap-labellings of some families of graphs (Q6048440)

The results of this paper fit inside the area of graph colouring. In particular, the authors study the so-called gap-labelling problem, in both its edge and vertex variants. More precisely, consider an assignment of integer values \(\{1, \dots , k\}\) to either the edges or vertices of a graph. In the edge-labelling variant, a vertex with degree of at least two has its colour defined by the largest difference, or the largest `gap', among the labels of its incident edges; vertices of degree 1 receive as induced colour the label assigned to its incident edge. For the vertex variant, the gaps are defined by the largest difference among the labels in the vertices neighbourhood, and degree-one vertices receive as colour the label assigned to their (only) neighbour. A gap-labelling is proper if the obtained colouring is proper and the least number \(k\) of labels for which a graph admits a proper gap-labelling of its edges (vertices) is called the edge-gap (vertex-gap) number of the graph. The contribution of this paper is the study of both parameters, from a structural and algorithmic point of view, for traditional families of graphs such as cycles, crowns and wheels. The authors also consider unicyclic graphs and several families of snarks.