publication . Preprint . 2012

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

Lu, Changhong; Zhou, Qing;
Open Access English
  • Published: 10 Apr 2012
Abstract
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 ...
Subjects
free text keywords: Mathematics - Combinatorics, Computer Science - Discrete Mathematics
Download from
35 references, page 1 of 3

[1] S. S. Adams, M. Tesch, D. S. Troxell and C. Wheeland, On the hole index of L(2, 1)-labelings of r-regular graphs, Discrete Appl. Math. 155 (2007), 2391- 2393.

[2] S. S. Adams, A. Trazkovich, D. S. Troxell and B. Westgate, On island sequences of labelings with a condition at distance two, Discrete Appl. Math. 158 (2010), 1-7.

[3] S. R. Arikati and C. P. Rangan, Linear algorithm for optimal path cover problem on interval graphs, Inform. Process. Lett. 35 (1990), 149-153.

[4] F. T. Boesch, S. Chen and N. A. M. McHugh, On covering the points of a graph with point disjoint paths, in: A. Dold, B. Eckman (Eds.), Graphs and Combinatorics, in: Lecture Notes in Math., vol. 406, Springer, Berlin, 1974, pp. 201-212.

[5] F. T. Boesch and J. F. Gimpel, Covering the points of a digraph with pointdisjoint paths and its application to code optimization, J. Assoc. Comput. 24 (1977), 192-198 [OpenAIRE]

[6] T. Calamoneri, The L(h, k)-labeling problem: A survey and annotated bibliography, Comput. J. 49 (2006), 585-608. [OpenAIRE]

[7] G. J. Chang and D. Kuo, The L(2, 1)-labeling on graphs, SIAM J. Discrete Math. 9 (1996), 309-316.

[8] P. Damaschke, J. S. Deogun, D. Kratsch and G. Steiner, Finding hamiltonian paths in cocomparability graphs using the bump number algorithm, Order 8 (1992), 383-391.

[9] P. C. Fishburn and F. S. Roberts, No-hole L(2, 1)-colorings, Discrete Appl. Math. 130 (2003), 513-519.

[10] P. C. Fishburn and F. S. Roberts, Full color theorems for L(2, 1)-labelings, SIAM J. Discrete Math. 20 (2006), 428-443.

[11] D. S. Franzblau and A. Raychaudhuri, Optimal hamiltonian completions and path covers for trees, and a reduction to maximum flow, Anziam J. 44 (2002), 193-204.

[12] J. Georges and D. W. Mauro, On the structure of graphs with non-surjective L(2, 1)-labelings, SIAM J. Discrete Math. 19 (2005), 208-223.

[13] J. Georges and D. W. Mauro, A note on collections of graphs with non-surjective lambda labelings, Discrete Appl. Math. 146 (2005), 92-98.

[14] J. Georges, D. W. Mauro and M. Whittlesey, Relating path covering to vertex labelings with a condition at distance two, Discrete Math. 135 (1994), 103-111.

[15] J. R. Griggs and R. K. Yeh, Labeling graphs with a condition at distance two, SIAM J. Discrete Math. 5 (1992), 586-595.

35 references, page 1 of 3
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue