PROPER AND UNIT TOLERANCE GRAPHS

被引：40

作者：

BOGART, KP

FISHBURN, PC

ISAAK, G

LANGLEY, L

机构：

[1] LEHIGH UNIV,DEPT MATH,BETHLEHEM,PA 18015

[2] DARTMOUTH COLL,HANOVER,NH 03755

[3] AT&T BELL LABS,MURRAY HILL,NJ 07974

来源：

DISCRETE APPLIED MATHEMATICS | 1995年 / 60卷 / 1-3期

关键词：

D O I：

10.1016/0166-218X(94)00044-E

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We answer a question of Golumbic, Monma and Trotter by constructing proper tolerance graphs that are not unit tolerance graphs. An infinite family of graphs that are minimal in this respect is specified.

引用

页码：99 / 117

页数：19

共 8 条

[1]

Golumbic M. C., 1980, ALGORITHMIC GRAPH TH

[2]

GOLUMBIC M. C., 1982, GRAPH THEORY COMPUT, P321

[3] TOLERANCE GRAPHS [J].

GOLUMBIC, MC ;

MONMA, CL ;

TROTTER, WT .

DISCRETE APPLIED MATHEMATICS, 1984, 9 (02) :157-170

[4]

Jacobson M. S., 1991, GRAPH THEORY COMB AP, P705

[5] GENERAL RESULTS ON TOLERANCE INTERSECTION GRAPHS [J].

JACOBSON, MS ;

MCMORRIS, FR ;

SCHEINERMAN, ER .

JOURNAL OF GRAPH THEORY, 1991, 15 (06) :573-577

[6]

Jacobson MS., 1991, J COMBIN INFORM SYST, V16, P25

[7] STABILITY NUMBER AND CHROMATIC NUMBER OF TOLERANCE GRAPHS [J].

NARASIMHAN, G ;

MANBER, R .

DISCRETE APPLIED MATHEMATICS, 1992, 36 (01) :47-56

[8]

Roberts F. S., 1969, PROOF TECHNIQUES GRA, P139

← 1 →