[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 Fangyun¹, Gu Guohua², Xu Kexiang³

¹Department of Mathematics of College of Information Science and Technology, Nanjing Forest University, Nanjing 210037, China
²Department of Mathematics, Southeast University, Nanjing 210096, China
³College of Science, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China

陶昉昀¹, 顾国华², 许克祥³

¹南京林业大学信息科学技术学院数学系, 南京 210037; ²东南大学数学系, 南京 210096; ³南京航空航天大学理学院, 南京 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)≤Δ².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∈N且k, 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 Q_n 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.

Common functions