Distance two labeling on the square of a cycle
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
An $L(2,1)$-labeling of a graph $G$ is a function $f$ from the vertex set $V(G)$ to the set of all non-negative integers such that $|f(u)-f(v)|\geq 2$ if $d(u,v)=1$ and $|f(u)-f(v)|\geq 1$ if $d(u,v)=2$. The $\lambda$-number of $G$, denoted $\lambda(G)$, is the smallest number $k$ such that $G$ admits an $L(2, 1)$-labeling with $k=\max\{f(u)|u\in V(G)\}$. In this paper, we consider the square of a cycle and provide exact value for its $\lambda$-number. In addition, we also completely determine its edge span.
Abstract
An $L(2,1)$-labeling of a graph $G$ is a function $f$ from the vertex set $V(G)$ to the set of all non-negative integers such that $|f(u)-f(v)|\geq 2$ if $d(u,v)=1$ and $|f(u)-f(v)|\geq 1$ if $d(u,v)=2$. The $\lambda$-number of $G$, denoted $\lambda(G)$, is the smallest number $k$ such that $G$ admits an $L(2, 1)$-labeling with $k=\max\{f(u)|u\in V(G)\}$. In this paper, we consider the square of a cycle and provide exact value for its $\lambda$-number. In addition, we also completely determine its edge span.
참고문헌 (21)
- T. Calamoneri, "L(h; 1)-labeling subclasses of planar graphs", J. Parall. Distrib. Comput, 64, pp.414~426 (2004)
- T. Calamoneri, "Exact solution of a class of frequency assignment problems in cellular networks and other regular grids", Theor. Comput. Sci, 8, pp.141~158 (2006)
- T. Calamoneri, "The L(h; k)-labelling problem: an updated survey and annotated bibliography", Computer J, 54, pp.1344~1371 (2011)
- G.J. Chang, "The L(2; 1)-labeling problem on graphs", SIAM J. Dis-crete Math, 9, pp.309~316 (1996)
- J.P. Georges, "Relating path coverings to vertex labellings with a condition at distance two", Discrete Math, 135, pp.103~111 (1994)
- J.R. Griggs, "Labeling graph with a condition at distance two", SIAM J. Discrete Math, 5, pp.586~595 (1992)
- J.R. Griggs, "Real number channel assignments with distance conditions", SIAM J. Discrete Math, 20, pp.302~327 (2006)
- W.K. Hale, "Frequency assignment: Theory and applications", Proc. IEEE, 68, pp.1497~1514 (1980)
- J. van den Heuvel, "Graph labelling and radio channel assignment", J. Graph Theory, 29, pp.263~283 (1998)
- L.-H. Huang, "L(h; k)-labelings of Hamming graphs", Discrete Math, 309, pp.2197~2201 (2009)
- N. Karst, "The minimum span of L(2; 1)-labelings of generalized owers", Discrete Appl. Math, 181, pp.139~151 (2015)
- M. Kochol, "Tension polynomials of graphs", J. Graph Theory, 3, pp.137~146 (2002)
- A. Kohl, "Knotenfarbungen mit Abstandsbedingungen", 박사, pp.2006
- D. Korze, "L(2; 1)-labeling of strong products of cycles", Inform. Process Lett, 94, pp.183~190 (2005)
- S. Paul, "L(2; 1)-Labeling of Permutation and Bipartite Permutation Graphs", Math. Comput. Sci, 9, pp.113~123 (2015)
- Z. Shao, "The L(2; 1)-labeling and operations of graphs", IEEE Trans. Circuits Syst. I Fund. Theory Appl, 52, pp.668~671 (2005)
- Z. Shao, "The L(2; 1)-labeling on planar graphs", Appl. Math. Lett, 20, pp.222~226 (2007)
- W.F. Wang, "The L(2; 1)-labelling of trees", Discrete Appl. Math, 154, pp.598~603 (2007)
- R.K. Yeh, "A survey on labeling graphs with a condition at distance two", Discrete Math, 306, pp.1217~1231 (2006)
- R.K. Yeh, "The edge span of distance two labelings of graphs", Taiwanese J. Math, 4, pp.675~683 (2000)
- X.L. Zhang, "L(p; q)-labeling and integer tension of a graph embedded on torus", J. Combin. Optim (2014)[DOI]