✦ LIBER ✦

Tolerance graphs

✍ Scribed by Martin Charles Golumbic; Clyde L. Monma; William T. Trotter Jr.

Publisher: Elsevier Science
Year: 1984
Tongue: English
Weight: 756 KB
Volume: 9
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(84)90016-7

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Tolerance competition graphs

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

Threshold tolerance graphs

✍ Clyde L. Monma; Bruce Reed; William T. Trotter Jr. 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 994 KB

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 in

Tolerance graphs, and orders

✍ Felsner, Stefan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 2 views

We show that, if a tolerance graph is the complement of a comparability graph, it is a trapezoid graph, i.e., the complement of an order of interval dimension at most 2. As consequences we are able to give obstructions for the class of bounded tolerance graphs and to give an example of a graph that

Archimedean ϕ -tolerance graphs

✍ Martin Charles Golumbic; Robert E. Jamison; Ann N. Trenk 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

## Abstract Let ϕ be a symmetric binary function, positive valued on positive arguments. A graph __G__ = (__V__,__E__) is a ϕ‐__tolerance graph__ if each vertex υ ∈ __V__ can be assigned a closed interval __I__~υ~ and a positive tolerance __t__~υ~ so that __xy__ ∈ __E__ ⇔ | __I__~x~ ∩ __I__~y~|≥ ϕ

Neighborhood subtree tolerance graphs

✍ Eric Bibelnieks; P.M. Dearing 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 906 KB

Node fault tolerance in graphs

✍ Harary, Frank; Hayes, John P. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 405 KB 👁 2 views

A graph G \* is a k-node fault-tolerant supergraph of a graph G , denoted k-NFT( G), if every graph obtained by removing k nodes from G\* contains G. A k-NFT(G) graph G\* is said to be optimal if it contains n + k nodes, where n is the number of nodes of G and G \* has the minimum number of edges am