More relations between $\lambda$-labeling and Hamiltonian paths with emphasis on line graph of bipartite multigraphs
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
This paper deals with the $\lambda$-labeling and $L(2,1)$-coloring of simple graphs. A $\lambda$-labeling of a graph $G$ is any labeling of the vertices of $G$ with different labels such that any two adjacent vertices receive labels which differ at least two. Also an $L(2,1)$-coloring of $G$ is any labeling of the vertices of $G$ such that any two adjacent vertices receive labels which differ at least two and any two vertices with distance two receive distinct labels. Assume that a partial $\lambda$-labeling $f$ is given in a graph $G$. A general question is whether $f$ can be extended to a $\lambda$-labeling of $G$. We show that the extension is feasible if and only if a Hamiltonian path consistent with some distance constraints exists in the complement of $G$. Then we consider line graph of bipartite multigraphs and determine the minimum number of labels in $L(2,1)$-coloring and $\lambda$-labeling of these graphs. In fact we obtain easily computable formulas for the path covering number and the maximum path of the complement of these graphs. We obtain a polynomial time algorithm which generates all Hamiltonian paths in the related graphs. A special case is the Cartesian product graph $K_n\Box K_n$ and the generation of $\lambda$-squares.
Abstract
This paper deals with the $\lambda$-labeling and $L(2,1)$-coloring of simple graphs. A $\lambda$-labeling of a graph $G$ is any labeling of the vertices of $G$ with different labels such that any two adjacent vertices receive labels which differ at least two. Also an $L(2,1)$-coloring of $G$ is any labeling of the vertices of $G$ such that any two adjacent vertices receive labels which differ at least two and any two vertices with distance two receive distinct labels. Assume that a partial $\lambda$-labeling $f$ is given in a graph $G$. A general question is whether $f$ can be extended to a $\lambda$-labeling of $G$. We show that the extension is feasible if and only if a Hamiltonian path consistent with some distance constraints exists in the complement of $G$. Then we consider line graph of bipartite multigraphs and determine the minimum number of labels in $L(2,1)$-coloring and $\lambda$-labeling of these graphs. In fact we obtain easily computable formulas for the path covering number and the maximum path of the complement of these graphs. We obtain a polynomial time algorithm which generates all Hamiltonian paths in the related graphs. A special case is the Cartesian product graph $K_n\Box K_n$ and the generation of $\lambda$-squares.
참고문헌 (26)
- H. L. Bodlaender, "Radio labeling with preassigned frequencies", SIAM J. Optim, 15(1), pp.1~16 (2004)[DOI]
- Hans L. Bodlaender, "λ-Coloring of Graphs", STACS 2000, pp.395~406 (2000), Springer Berlin Heidelberg
- J. S. Deogun, "1-tough cocomparability graphs are Hamiltonian", Discrete Math, 170(1-3), pp.99~106 (1997)[DOI]
- J. Fiala, "Fixed-parameter complexity of λ-labelings", Discrete Appl. Math, 113(1), pp.59~72 (2001)[DOI]
- Jiři Fiala, "Distance Constrained Labeling of Precolored Trees", Lecture Notes in Computer Science, pp.285~292 (2001), Springer Berlin Heidelberg
- D. A. Fotakis, "Hardness results and efficient approximations for frequency assignment problems : radio labelling and radio coloring", Comput. Inform, 20(2), pp.121~180 (2001)
- Dimitris A. Fotakis, "A Hamiltonian Approach to the Assignment of Non-reusable Frequencies", Lecture Notes in Computer Science, pp.18~29 (1998), Springer Berlin Heidelberg
- J. P. Georges, "Labeling products of complete graphs with a condition at distance two", SIAM J. Discrete Math, 14(1), pp.28~35 (2001)[DOI]
- J. P. Georges, "Relating path coverings to vertex labellings with a condition at distance two", Discrete Math, 135(1-3), pp.103~111 (1994)[DOI]
- J. R. Griggs, "Labelling graphs with a condition at distance 2", SIAM J. Discrete Math, 5(4), pp.586~595 (1992)[DOI]
- H. Hajiabolhassan, "Tabular graphs and chromatic sum", Discrete Math, 304(1-3), pp.11~22 (2005)[DOI]
- Y. -Z. Huang, "On L(2, 1)-labeling of generalized Petersen graphs", J. Comb. Optim, 24(3), pp.266~279 (2012)[DOI]
- David Kuo, "On L(2,1)-labelings of Cartesian products of paths and cycles", Discrete Mathematics, 283(1-3), pp.137~144 (2004), Elsevier BV[DOI]
- B. Li, "Forbidden subgraphs for Hamiltonicity of 1-tough graphs", Discuss. Math. Graph Theory, 36(4), pp.915~929 (2016)[DOI]
- Xiangwen Li, "Hamilton cycles in 1-tough triangle-free graphs", Discrete Mathematics, 254(1-3), pp.275~287 (2002), Elsevier BV[DOI]
- L Lovász, "On a product dimension of graphs", Journal of Combinatorial Theory, Series B, 29(1), pp.47~67 (1980), Elsevier BV[DOI]
- D. Lu, "Distance two labelings of Cartesian products of complete graphs", Ars Combin, 104, pp.33~40 (2012)
- Changhong Lu, "Path covering number and L(2, 1)-labeling number of graphs", Discrete Applied Mathematics, 161(13-14), pp.2062~2074 (2013), Elsevier BV[DOI]
- F. Maffray, "A description of claw-free perfect graphs", J. Combin. Theory Ser. B, 75(1), pp.134~156 (1999)[DOI]
- L. Rao, "Graph theory, combinatorics, and algorithms, Vol. 1, 2", pp.977~980 (1995), Wiley-Intersci. Publ, Wiley
- U. Sarkar, "On characterizing radio k-coloring problem by path covering problem", Discrete Math, 338(4), pp.615~620 (2015)[DOI]
- Christopher Schwarz, "L(2, 1)-labelings of Cartesian products of two cycles", Discrete Applied Mathematics, 154(10), pp.1522~1540 (2006), Elsevier BV[DOI]
- Z. Shao, "On some results for the L(2, 1)-labeling on Cartesian sum graphs", Ars Combin, 124, pp.365~377 (2016)
- Z. Shao, "The L(2, 1)-labeling on graphs and the frequency assignment problem", Appl. Math. Lett, 21(1), pp.37~41 (2008)[DOI]
- B. Wei, "Hamiltonian cycles in 1-tough graphs", Graphs Combin, 12(4), pp.385~395 (1996)[DOI]
- R. K. Yeh, "A survey on labeling graphs with a condition at distance two", Discrete Math, 306(12), pp.1217~1231 (2006)[DOI]