[1] Tao Fangyun, Gu Guohua,. L(2, 1)-labeling problem on distance graphs [J]. Journal of Southeast University (English Edition), 2004, 20 (1): 122-125. [doi:10.3969/j.issn.1003-7985.2004.01.025]
Copy
L(2, 1)-labeling problem on distance graphs(
)
)Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]
- Volumn:
- 20
- Issue:
- 2004 1
- Page:
- 122-125
- Research Field:
- Mathematics, Physics, Mechanics
- Publishing date:
- 2004-03-30
Info
- Title:
- L(2, 1)-labeling problem on distance graphs
- Author(s):
- Tao Fangyun; Gu Guohua
- Department of Mathematics, Southeast University, Nanjing 210096, China
- Keywords:
- L(2; 1)-labeling; distance graph; channel assignment problem
- PACS:
- O157.5
- DOI:
- 10.3969/j.issn.1003-7985.2004.01.025
- Abstract:
- L(2, 1)-labeling number, λ(G(Z, D)), of distance graph G(Z, D) is studied. For general finite distance set D, it is shown that 2|D|+2≤λ(G(Z, D))≤|D|2+3|D|. Furthermore, λ(G(Z, D))≤8 when D consists of two prime positive odd integers is proved. Finally, a new concept to study the upper bounds of λ(G) for some special D is introduced. For these sets, the upper bound is improved to 7.
References:
[1] Hale W K. Frequency assignment: theory and applications [J]. Proc IEEE, 1980, 68(12): 1497-1514.
[2] Griggs J R, Yeh R K. Labeling graphs with a condition at distance 2 [J]. SIAM J Discrete Math, 1992, 5(4): 586-595.
[3] Yeh R K. Labeling graphs with a condition at distance two [D]. Columbia, SC: Department of Mathematics, University of South Carolina, 1990.
[4] Chang G J, Kuo D. The L(2, 1)-labeling problem on graphs [J]. SIAM J Discrete Math, 1996, 9(2): 309-316.
[5] Sakai D. Labeling chordal graphs: distance two condition [J]. SIAM J Discrete Math, 1994, 7(1): 103-111.
[6] Georges J P, Mauro D W, Stein M I. Labeling products of complete graphs with a condition at distance two [J]. SIAM J Discrete Math, 2000, 14(1): 28-35.
[7] Jha P K, Narayanan A, Sood P, et al. On L(2, 1)-labeling of the Cartesian product of a cycle and a path [J]. Ars Combinatoria, 2000, 55(April): 81-89.
[8] Chang G J, Ke W T, Kuo D, et al. On L(d, 1)-labelings of graphs [J]. Discrete Mathematics, 2000, 220(1-3): 57-66.
[9] Jonas K. Graph colorings analogues with a condition at distance two: L(2, 1)-labelings and list-labelings [D]. Columbia, SC: Department of Mathematics, University of South Carolina, 1993.
[10] Whittlesey M A, Georges J P, Mauro D W. On the λ-number of Qn and related graphs [J]. SIAM J Discrete Math, 1995, 8(4): 499-506.
[11] Eggleton R B, Erdös P, Skilton D K. Coloring the real line [J]. J Combin Theory, Series B, 1985, 39: 86-100.
[12] Frobenius G. über matrizen aus nichtnegativen elementen [M]. Akad Wiss Berlin: Sitzungsberichte Preuss, 1912. 456-477.
Memo
- Memo:
- Biographies: Tao Fangyun(1979—), female, graduate; Gu Guohua(corresponding author), male, professor.