LABELING GRAPHS WITH A CONDITION AT DISTANCE-2

被引:537
作者
GRIGGS, JR
YEH, RK
机构
关键词
T-COLORING; CHANNEL ASSIGNMENTS; GRAPH COLORING; NP-COMPLETENESS;
D O I
10.1137/0405048
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Given a simple graph G = (V, E) and a positive number d, an L(d)(2, 1)-labelling of G is a function f : V(G) --> [0, infinity) such that whenever x, y is-an-element-of V are adjacent, \f(x) - f(y)\ greater-than-or-equal-to 2d, and whenever the distance between x and y is two, \f(x) - f(y)\ greater-than-or-equal-to d. The L(d) (2, 1)-labelling number lambda(G, d) is the smallest number m such that G has an L(d)(2, 1)-labelling f with max {f(v) : v is-an-element-of V} = m. It is shown that to determine lambda(G, d), it suffices to study the case when d = 1 and the labelling is nonnegative integral-valued. Let lambda(G) = lambda(G, 1). The labelling numbers of special classes of graphs, e.g., lambda(C) = 4 for any cycle C, are described. It is shown that for graphs of maximum degree DELTA, lambda(G) less-than-or-equal-to DELTA2 + 2DELTA. If G is diameter 2, lambda(G) less-than-or-equal-to DELTA2, a sharp bound for some A. Determining lambda(G) is shown to be NP-complete by relating it to the problem of finding Hamilton paths.
引用
收藏
页码:586 / 595
页数:10
相关论文
共 20 条
[1]  
Bollobas B., 1978, LONDON MATH SOC MONO
[2]  
BONDY JA, 1976, GRAPH THEORY APPLICA
[3]  
Cozzens M. B., 1982, C NUMER, V35, P191
[4]  
Dirac G. A., 1952, P LOND MATH SOC, V2, P69, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]
[5]  
Furedi Z., 1989, SIAM J DISCRETE MATH, V4, P491
[6]  
Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[7]  
Golumbic M. C., 1980, ALGORITHMIC GRAPH TH
[8]   FREQUENCY ASSIGNMENT - THEORY AND APPLICATIONS [J].
HALE, WK .
PROCEEDINGS OF THE IEEE, 1980, 68 (12) :1497-1514
[9]   ON MOORE GRAPHS WITH DIAMETER-2 AND DIAMETER-3 [J].
HOFFMAN, AJ ;
SINGLETON, RR .
IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1960, 4 (05) :497-504
[10]  
JONAS K, 1991, COMMUNICATION