|Table of Contents|

[1] Tao Fangyun, Gu Guohua, Xu Kexiang,. On L(2, 1)-labellings of distance graphs [J]. Journal of Southeast University (English Edition), 2005, 21 (2): 244-248. [doi:10.3969/j.issn.1003-7985.2005.02.026]
Copy

On L(2, 1)-labellings of distance graphs()
关于距离图的L(2, 1)-标号着色
Share:

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:
21
Issue:
2005 2
Page:
244-248
Research Field:
Mathematics, Physics, Mechanics
Publishing date:
2005-06-30

Info

Title:
On L(2, 1)-labellings of distance graphs
关于距离图的L(2, 1)-标号着色
Author(s):
Tao Fangyun1 Gu Guohua2 Xu Kexiang3
1Department of Mathematics of College of Information Science and Technology, Nanjing Forest University, Nanjing 210037, China
2Department of Mathematics, Southeast University, Nanjing 210096, China
3College of Science, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
陶昉昀1 顾国华2 许克祥3
1南京林业大学信息科学技术学院数学系, 南京 210037; 2东南大学数学系, 南京 210096; 3南京航空航天大学理学院, 南京 210016
Keywords:
channel assignment problem L(2 1)-labelling distance graphs
频道分配问题 L(2 1)-标号着色 距离图
PACS:
O157.5
DOI:
10.3969/j.issn.1003-7985.2005.02.026
Abstract:
The L(2, 1)-labelling number of distance graphs G(D), denoted by λ(D), is studied.It is shown that distance graphs satisfy λ(G)≤Δ2.Moreover, we prove λ({1, 2, …, k})=2k+2 and λ({1, 3, …, 2k-1})=2k+2 for any fixed positive integer k.Suppose k, a∈N and k, a≥2.If k≥a, then λ({a, a+1, …, a+k-1})=2(a+k-1).Otherwise, λ({a, a+1, …, a+k-1})min{2(a+k-1), 6k-2}.When D consists of two positive integers, 6≤λ(D)≤8.For the special distance sets D={k, k+1}(∠k∈N), the upper bound of λ(D)is improved to 7.
研究了距离图G(D)的L(2, 1)-标号色数λ(D).证明了距离图满足λ(G)≤Δ2.2对于任意给定的正整数k, 证明了λ({1, 2, …, k})=2k+2和λ({1, 3…, 2k-1})=2k+2.假设k, a∈Nk, a≥2.如果k≥a, λ({a, a+1, …, a+k-1})=2(a+k-1).否则, λ({a, a+1, …, a+k-1})min{2(a+k-1), 6k-2}.D由2个正整数构成, 则6≤λ(D)8.对于特殊的距离集D={k, k+1}(∠k∈N), λ(D)的上界改进到了7.

References:

[1] Hale W K.Frequency assignment:theory and applications [J].Proceedings of the IEEE, 1980, 68(12):1497-1514.
[2] Griggs J R, Yeh R K.Labelling graphs with a condition at distance 2 [J].SIAM J Discrete Math, 1992, 5(4):586-595.
[3] Chang G J, Kuo D.The L(2, 1)-labelling problem on graphs [J]. SIAM J Discrete Math, 1996, 9(2):309-316.
[4] 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.
[5] Sakai D.Labelling chordal graphs:distance two condition [J].SIAM J Discrete Math, 1994, 7(1):133-140.
[6] Georges J P, Mauro D W, Stein M I.Labelling products of complete graphs with a condition at distance 2[J].SIAM J Discrete Math, 2000, 14(1):28-35.
[7] Chang G J, Ke W T, Kuo D, et al.On L(d, 1)-labellings of graphs [J].Discrete Mathematics, 2000, 220(1-3):57-66.
[8] Tao F Y, Gu G H.L(2, 1)-labelling problem on distance graphs [J].Journal of Southeast University (English Edition), 2004, 20(1):122-125.
[9] Frobenius G.über Matrizen aus nichtnegativen elementen [M].Akad Wiss Berlin:Sitzungsberichte Preuss, 1912.456-477.

Memo

Memo:
Biography: Tao Fangyun(1979—), female, master, winnietfy@sina.com.cn.
Last Update: 2005-06-20