RELATING PATH COVERINGS TO VERTEX LABELINGS WITH A CONDITION AT DISTANCE-2

被引：122

作者：

GEORGES, JP ^{[1
]}

MAURO, DW ^{[1
]}

WHITTLESEY, MA ^{[1
]}

机构：

[1] UNIV OXFORD TRINITY COLL,DEPT MATH,HARTFORD,CT 06106

来源：

DISCRETE MATHEMATICS | 1994年 / 135卷 / 1-3期

关键词：

HAMILTON PATH; LAMBDA-LABELING; PATH COVERING;

D O I：

10.1016/0012-365X(93)E0098-O

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A lambda-labelling of graph G is an integer labelling of V(G) such that adjacent vertices have labels that differ by at least two and vertices distance two apart have labels that differ by at least one. The lambda number of G, lambda(G), is the minimum span of labels over all such labellings. Griggs and Yeh have studied the relationship between lambda(G) and graph invariants (chi)(G) and Delta(G). In this paper, we derive the relationship between lambda(G) and another graph invariant, the path covering number of G(c). Applications include the determination of the lambda-number of the join of two graphs, the product of two complete graphs, and the complete multi-partite graphs.

引用

页码：103 / 111

页数：9

共 12 条

[1]

BOESCH FT, 1974, 1973 P CAP C GRAPH T, P201

[2]

BONDY JA, 1976, GRAPH THEORY APPLICA

[3]

DIRAC GA, 1952, P LOND MATH SOC, P69

[4]

GRIGGS JR, IN PRESS SIAM J DISC

[5] FREQUENCY ASSIGNMENT - THEORY AND APPLICATIONS [J].

HALE, WK .

PROCEEDINGS OF THE IEEE, 1980, 68 (12) :1497-1514

[6] COVERING VERTICES OF A GRAPH BY VERTEX-DISJOINT PATHS [J].

NOORVASH, S .

PACIFIC JOURNAL OF MATHEMATICS, 1975, 58 (01) :159-168

[7]

Ore O, 1961, ANN MAT PUR APPL, V55, P315

[8]

ROBERTS FS, IN PRESS DISCRETE MA

[9]

ROBERTS FS, 1990, 6TH P INT C THEOR AP

[10]

SAKAI D, IN PRESS DISCRETE AP

← 1 2 →