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

Changhong Lu, Qing Zhou

Published 2012-04-10Version 1

A {\it path covering} of a graph $G$ is a set of vertex disjoint paths of $G$ containing all the vertices of $G$. The {\it path covering number} of $G$, denoted by $P(G)$, is the minimum number of paths in a path covering of $G$. An {\sl $k$-L(2,1)-labeling} of a graph $G$ is a mapping $f$ from $V(G)$ to the set ${0,1,...,k}$ such that $|f(u)-f(v)|\ge 2$ if $d_G(u,v)=1$ and $|f(u)-f(v)|\ge 1$ if $d_G(u,v)=2$. The {\sl L(2,1)-labeling number $\lambda (G)$} of $G$ is the smallest number $k$ such that $G$ has a $k$-L(2,1)-labeling. The purpose of this paper is to study path covering number and L(2,1)-labeling number of graphs. Our main work extends most of results in [On island sequences of labelings with a condition at distance two, Discrete Applied Maths 158 (2010), 1-7] and can answer an open problem in [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005), 208-223].