✦ LIBER ✦

Threshold tolerance graphs

✍ Scribed by Clyde L. Monma; Bruce Reed; William T. Trotter Jr.

Publisher: John Wiley and Sons
Year: 1988
Tongue: English
Weight: 994 KB
Volume: 12
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190120307

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we introduce a class of graphs that generalize threshold graphs by introducing threshold tolerances. Several characterizations of these graphs are presented, one of which leads to a polynomial-time recognition algorithm. It is also shown that the complements of these graphs contain interval graphs and threshold graphs, and are contained in the subclass of chordal graphs called strongly chordal graphs, and in the class of interval tolerance graphs.

📜 SIMILAR VOLUMES

ø-threshold and ø-tolerance chain graphs

✍ M.S. Jacobson; J. Lehel; L.M. Lesniak 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 732 KB

Tolerance graphs

✍ Martin Charles Golumbic; Clyde L. Monma; William T. Trotter Jr. 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 756 KB

Tolerance competition graphs

✍ R.C. Brigham; F.R. McMorris; R.P. Vitray 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 877 KB

Box-threshold graphs

✍ Uri N. Peled; Bruno Simeone 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 608 KB

A graph is called box-threshold when all pairs of vertices with incomparable neighborhoods have the same degree. Several properties of box-threshold graphs, generalizing properties of threshold graphs, are proved. A transportation model with priority constraints is used to characterize their degree

Quasi-threshold graphs

✍ Yan Jing-Ho; Chen Jer-Jeong; Gerard J. Chang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 589 KB

Hamiltonian threshold graphs

✍ Frank Harary; Uri Peled 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 258 KB