Path covering number and L(2,1)L(2,1)-labeling number of graphs

A path covering   of a graph GG is a set of vertex disjoint paths of GG containing all the vertices of GG. The path covering number   of GG, denoted by P(G)P(G), is the minimum number of paths in a path covering of GG. A kk-L(2,1)L(2,1)-labeling   of a graph GG is a mapping ff from V(G)V(G) to the set {0,1,…,k}{0,1,…,k} such that |f(u)−f(v)|≥2|f(u)−f(v)|≥2 if dG(u,v)=1dG(u,v)=1 and |f(u)−f(v)|≥1|f(u)−f(v)|≥1 if dG(u,v)=2dG(u,v)=2. The L(2,1)L(2,1)-labeling number  λ(G)λ(G) of GG is the smallest number kk such that GG has a kk-L(2,1)L(2,1)-labeling. The purpose of this paper is to study path covering numbers and L(2,1)L(2,1)-labeling numbers of graphs. Our main work extends most of the results in [S.S. Adams, A. Trazkovich, D.S. Troxell, B. Westgate, On island sequences of labelings with a condition at distance two, Discrete Appl. Math. 158 (2010) 1–7] and can answer an open problem in [J. Georges, D.W. Mauro, On the structure of graphs with non-surjective LL(2, 1)-labelings, SIAM J. Discrete Math. 19 (2005) 208–223].