The λ-number of the Cartesian product of a complete graph and a cycle
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
An L(j, k)-labeling of a graph G is a vertex labelingsuch that the difference of the labels of any adjacent vertices is atleast j and that of any vertices of distance two is at least k for givenj and k. The minimum span of all L(2, 1)-labelings of G is calledthe λ-number of G and is denoted by λ(G). In this paper, we find a lower bound of the λ-number of theCartesian product Km□Cn of the complete graph Km of order mand the cycle Cn of order n. In fact, we show that when n ≥ 3,λ(K4□Cn) ≥ 7 and the equality holds if and only if n is a multipleof 8. Moreover when m ≥ 5, λ(Km□Cn) ≥ 2m− 1 and the equalityholds if and only if n is even.
Abstract
An L(j, k)-labeling of a graph G is a vertex labelingsuch that the difference of the labels of any adjacent vertices is atleast j and that of any vertices of distance two is at least k for givenj and k. The minimum span of all L(2, 1)-labelings of G is calledthe λ-number of G and is denoted by λ(G). In this paper, we find a lower bound of the λ-number of theCartesian product Km□Cn of the complete graph Km of order mand the cycle Cn of order n. In fact, we show that when n ≥ 3,λ(K4□Cn) ≥ 7 and the equality holds if and only if n is a multipleof 8. Moreover when m ≥ 5, λ(Km□Cn) ≥ 2m− 1 and the equalityholds if and only if n is even
참고문헌 (19)
- S.S. Adams, "An extension of the channel- assignment problem: L(2; 1)-labelings of generalized Petersen graphs", IEEE Trans. Circ. Sys. I-Regular Papers, 53, pp.1101~1107 (2006)
- T. Calamoneri, "The L(h; k)-labeling problem: A survey and annotated biblog- raphy", Computer Journal, 49, pp.585~608 (2006)
- T. Calamoneri, "The L(h, k)-labeling problem: An updated survey and anno- tated biblography", Computer Journal, 54, pp.1344~1371 (2011)
- R. Erman, "Optimal real number graph labellings of a subfamily of Kneser graphs", SIAM J. Disc. Math, 23, pp.1372~1381 (2009)
- J.R. Griggs, "Recent progress in mathematics and engineering on optimal graph labelings with distance conditions", J. of Comb. Optim, 14, pp.249~257 (2007)
- J.R. Griggs, "Labeling graphs with acondition at distance two", SIAM J. Disc. Math, 5, pp.586~595 (1992)
- J.P. Georges, "Labeling products of complete graphs with a condition at a distance two", SIAM J. Disc. Math, 14, pp.2~35 (2000)
- W.K. Hale, "Frequency assignment: theory and application", Proc. IEEE, 68, pp.1497~1514 (1980)
- E. Haque, "L(j, k)-labelings of Kronecker products of complete graphs", IEEE Trans. on Cir. and Sys. II, 55, pp.70~73 (2008)
- F. Havet, "Griggs and Yeh's Conjecture and L(p, 1)- labelings", SIAM J. Disc. Math, 26, pp.145~168 (2012)
- P.K. Jha, "Optimal L(d, 1)-labelings of certain direct products of cycles and Cartesian product of cycles", Disc. Appl. Math, 152, pp.257~265 (2005)
- J. Kang, "L(2, 1)-labeling of hamiltonian graphs with maximum degree 3", SIAM J. Disc. Math, 22, pp.213~230 (2008)
- S. Klavzˇar, "The Δ2-conjecture for L(2, 1)-labelings is true for directed and strong products of graphs", IEEE Trans. Circuits Syst. II, 53, pp.274~277 (2006)
- B. Kim, "Labeling products of complete graphs with a condition at a distance two", International J. Computer Mathematics
- W. Lin, "Distance two labeling and direct products of graphs", Disc. Math, 308, pp.3805~3815 (2008)
- P. Lam, "L(j, k)-labelings for the products of complete graphs", J. of Comb. Optim, 14, pp.219~227 (2007)
- C. Schwartz, "L(2, 1)−labelings of Cartesian product of two cycles", Disc. Appl. Math, 154, pp.1522~1540 (2006)
- Z.D. Shao, "The L(2, 1)-labeling and operations of graphs", IEEE Trans. Circ. Sys. I-Regular Papers, 52, pp.668~671 (2005)
- M.A. Whittlesey, "On the λ-number of Qn and related graphs", SIAM J. Disc. Math, 8, pp.499~506 (1995)