2012/04/10 by Changhong Lü, Qing Zhou, Lu, Changhong +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1204.2306
openalex publication_date 2012/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)|≥ 2 if dG(u,v)=1 and |f(u)-f(v)|≥ 1 if dG(u,v)=2. The \sl L(2,1)-labeling number λ(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].