✦ LIBER ✦

Box-threshold graphs

✍ Scribed by Uri N. Peled; Bruno Simeone

Publisher: John Wiley and Sons
Year: 1984
Tongue: English
Weight: 608 KB
Volume: 8
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190080213

No coin nor oath required. For personal study only.

✦ Synopsis

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 sequences. Further characterizations are given using the concept of the frame of a graph.

1. Introduction

We consider finite undirected loopless graphs without multiple edges, except that loops will be used in Section 4. For graph G(V,E), the vicinal preorder 3 on V is defined by

That is, x a y if and only if every neighbor of y is a neighbor of x or x itself.

Graph G is a threshold graph when its vicinal preorder is a total (linear)

order. This means that there do not exist incomparable vertices, i.e.,

📜 SIMILAR VOLUMES

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

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

Longest cycles in threshold graphs

✍ N.V.R. Mahadev; U.N. Peled 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 495 KB

Graphs of nonsingular threshold transfor

Graphs of nonsingular threshold transformations

✍ Takao Ueda 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 695 KB

After the graph structures of self-dual nonsingular (i.e. one-to-one) transformations of (0, 1)" are described, a construction method of generating minimal nonsingular threshold transformations from lower-dimensional ones is presented. Theorems which concern nonsingular threshold transformations and

Multidimensional scaling and threshold g

Multidimensional scaling and threshold graphs

✍ Margaret B. Cozzens; Rochelle Leibowitz 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 642 KB