|Table of Contents|

[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()
图的L(d, 1)-标号的边跨度
Share：

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
图的L(d, 1)-标号的边跨度
Author(s):
Feng Guizhen, Song Zengmin
Department of Mathematics, Southeast University, Nanjing 210096, China
东南大学数学系, 南京 210096
Keywords:
L(d;  1)-labeling;  edge span;  triangular lattice;  square lattice;  choral graphs;  r-path
L(d;  1)-标号;  边跨度;  正三角形网格;  正四边形网格;  弦图;  r-路
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.
对于给定图G顶点集上一个非负整数函数f, 满足:若dG(u, v)=1, |f(u)-f(v)|≥d;若 dG(u, v)=2, |f(u)-f(v)|≥1.称f 为L(2, 1)-标号.这是由频道分配问题抽象出来的数学模型.本文主要研究该标号问题的一个参数, 即边跨度, 记作βd(G)=minmax{|f(u)-f(v)|:∠u∈V(G)}, 即对于所有正常的L(d, 1)-标号, 使得相邻顶点标号之差的最大值达到最小.本文主要讨论了圈Cn、树T、 k-部完全图、正三角形网格、 正四边形网格以及弦图等图类的边跨度, 并给出了确切的数值.

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.
Last Update: 2005-03-20