✦ LIBER ✦

Tolerance graphs, and orders

✍ Scribed by Felsner, Stefan

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 105 KB
Volume: 28
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199807)28:3<129::aid-jgt2>3.0.co;2-m

No coin nor oath required. For personal study only.

✦ Synopsis

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 is alternatingly orientable but not a tolerance graph. We also characterize the tolerance graphs among complements of trees.

📜 SIMILAR VOLUMES

Node fault tolerance in graphs

✍ Harary, Frank; Hayes, John P. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 405 KB 👁 1 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

Fault-tolerant graphs for tori

✍ Yamada, Toshinori; Ueno, Shuichi 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 1 views

Motivated by the design of fault-tolerant multiprocessor interconnection networks, this paper considers the following problem: Given a positive integer t and a graph H, construct a graph G from H by adding a minimum number D(t, H) of edges such that even after deleting any t edges from G the remaini

Onk-ordered Hamiltonian graphs

✍ Kierstead, H. A.; S�rk�zy, G. N.; Selkow, S. M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB 👁 1 views

the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine

k-ordered Hamiltonian graphs

✍ Ng, Lenhard; Schultz, Michelle 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 2 views

A hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v 1 , v 2 , . . . , v k of k distinct vertices of G, there exists a hamiltonian cycle that encounters v 1 , v 2 , . . . , v k in this order. Theorems by Dirac and Ore, presenting sufficient conditions for a graph to be h

On k-ordered graphs

✍ Jill R. Faudree; Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Linda L 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 1 views

Degree sequences of graphs and dominance

Degree sequences of graphs and dominance order

✍ Triesch, Eberhard 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 271 KB 👁 1 views

Suppose that the graphical partition H(A) = (a: 2 . . . 2 a:) arises from A = (al 2 . . . 2 a,) by deleting the largest summand a1 from A and reducing the a1 largest of the remaining summands by one. Let (a;+l 2 . . 2 ah) = H ( A ) denote the partition obtained by applying the operator H i times. We