[1] Feng Guizhen, Song Zengmin,. Edge span of L(d, 1)-labeling on some graphs [J]. Journal of Southeast University (English Edition), 2005, 21 (1): 111-114. [doi:10.3969/j.issn.1003-7985.2005.01.024]
Copy
Edge span of L(d, 1)-labeling on some graphs(
)
)Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]
- Volumn:
- 21
- Issue:
- 2005 1
- Page:
- 111-114
- Research Field:
- Mathematics, Physics, Mechanics
- Publishing date:
- 2005-03-30
Info
- Title:
- Edge span of L(d, 1)-labeling on some graphs
- Author(s):
- Feng Guizhen; Song Zengmin
- Department of Mathematics, Southeast University, Nanjing 210096, China
- Keywords:
- L(d; 1)-labeling; edge span; triangular lattice; square lattice; choral graphs; r-path
- PACS:
- O157.5
- DOI:
- 10.3969/j.issn.1003-7985.2005.01.024
- Abstract:
- Given a graph G and a positive integer d, an L(d, 1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that |f(u)-f(v)|≥d if dG(u, v)=1;|f(u)-f(v)|≥1 if dG(u, v)=2.The L(d, 1)-labeling number of G, λd(G)is the minimum range span of labels over all such labelings, which is motivated by the channel assignment problem.We consider the question of finding the minimum edge span βd(G)of this labeling.Several classes of graphs such as cycles, trees, complete k-partite graphs, chordal graphs including triangular lattice and square lattice which are important to a telecommunication problem are studied, and exact values are given.
References:
[1] Griggs J G, Yeh R K.Labeling graphs with a condition at distance two [J].SIAM J Discrete Math, 1992, 5(4):586-595.
[2] Hale W K. Frequency assignment:theory and applications[J].Proceedings of the IEEE, 1980, 68(12):1497-1514.
[3] Chang G J, Kuo D.The L(2, 1)-labeling on graphs [J].SIAM J Discrete Math, 1996, 9(2):309-316.
[4] Chang G J, Ke W T, Kuo D, et al.On L(d, 1)-labelings of graphs [J].Discrete Math, 2000, 220(1-3):57-66.
[5] Yeh R K.The edge span of distance two labelings of graphs [J].Taiwanese J Math, 2000, 4(4):675-683.
[6] Wu K F, Yeh R K.Labeling graphs with the circular difference [J].Taiwanese J Math, 2000, 4(3):397-405.
[7] 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.
[8] Sakai D.Labeling chordal graphs:distance two condition [J].SIAM J Discrete Math, 1994, 7(1):133-140.
[9] Georges J P, Mauro D W, Whittlesey M A.Relating path covering to vertex labelings with a condition at distance two [J].Discrete Math, 1994, 135:103-111.
[10] Bondy J A, Marty U S R.Graph theory with applications[M].New York:Maclmillan Press Ltd, 1976.
Memo
- Memo:
- Biographies: Feng Guizhen(1979—), female, graduate;Song Zengmin(corresponding author), male, doctor, professor, zmsong@seu.edu.cn.