On island sequences of labelings with a condition at distance two

An L(2,1)L(2,1)-labeling   of a graph GG is a function ff from the vertex set of GG to the set of nonnegative integers such that |f(x)−f(y)|≥2|f(x)−f(y)|≥2 if d(x,y)=1d(x,y)=1, and |f(x)−f(y)|≥1|f(x)−f(y)|≥1 if d(x,y)=2d(x,y)=2, where d(x,y)d(x,y) denotes the distance between the pair of vertices x,yx,y. The lambda number   of GG, denoted λ(G)λ(G), is the minimum range of labels used over all LL(2,1)-labelings of GG. An LL(2,1)-labeling of GG which achieves the range λ(G)λ(G) is referred to as a λλ-labeling. A hole   of an LL(2,1)-labeling is an unused integer within the range of integers used. The hole index   of GG, denoted ρ(G)ρ(G), is the minimum number of holes taken over all its λλ-labelings. An island   of a given λλ-labeling of GG with ρ(G)ρ(G) holes is a maximal set of consecutive integers used by the labeling. Georges and Mauro [J.P. Georges, D.W. Mauro, On the structure of graphs with non-surjective LL(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208–223] inquired about the existence of a connected graph GG with ρ(G)≥1ρ(G)≥1 possessing two λλ-labelings with different ordered sequences of island cardinalities. This paper provides an infinite family of such graphs together with their lambda numbers and hole indices. Key to our discussion is the determination of the path covering number of certain 2-sparse graphs, that is, graphs containing no pair of adjacent vertices of degree greater than 2.