✦ LIBER ✦

Extremal interval graphs

✍ Scribed by Jürgen Eckhoff

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 471 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170112

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An interval graph is said to be extremal if it achieves, among all interval graphs having the same number of vertices and the same clique number, the maximum possible number of edges. We give an intrinsic characterization of extremal interval graphs and derive recurrence relations for the numbers of such graphs. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Extremal graphs for homomorphisms

✍ Jonathan Cutler; A. J. Radcliffe 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

The study of graph homomorphisms has a long and distinguished history, with applications in many areas of graph theory. There has been recent interest in counting homomorphisms, and in particular on the question of finding upper bounds for the number of homomorphisms from a graph G into a fixed imag

Random interval graphs

✍ Nicholas Pippenger 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 1 views

We consider models for random interval graphs that are based on stochastic service systems, with vertices corresponding to customers and edges corresponding to pairs of customers that are in the system simultaneously. The number N of vertices in a connected component thus corresponds to the number o

Pseudo-Interval Graphs

✍ Erik O. Brauner; Richard A. Brauldi; Elizabeth S. N. Sneyd 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 431 KB

## Abstract We study a class of perfect graphs which, because they generalize interval graphs, we call pseudo‐interval graphs. Like interval graphs, their vertices correspond to intervals of a linearly ordered set, but a modified definition of intersection is used in order to determine edges. The c

Extremal graphs in connectivity augmenta

Extremal graphs in connectivity augmentation

✍ Jord�n, Tibor 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 245 KB 👁 1 views

Let A(n, k, t) denote the smallest integer e for which every kconnected graph on n vertices can be made (k + t)-connected by adding e new edges. We determine A(n, k, t) for all values of n, k, and t in the case of (directed and undirected) edge-connectivity and also for directed vertex-connectivity

Extremal maximal uniquely hamiltonian gr

Extremal maximal uniquely hamiltonian graphs

✍ Curtiss A. Barefoot; R. C. Entringer 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 352 KB

## Abstract Let __G__ be a graph of order __n__ with exactly one Hamiltonian cycle and suppose that __G__ is maximal with respect to this property. We determine the minimum number of edges __G__ can have.

Det-extremal cubic bipartite graphs

✍ M. Funk; Bill Jackson; D. Labbate; J. Sheehan 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

## Abstract Let __G__ be a connected __k__–regular bipartite graph with bipartition __V__(__G__) = __X__ ∪ __Y__ and adjacency matrix __A__. We say __G__ is det‐extremal if __per__ (__A__) = |__det__(A)|. Det–extremal __k__–regular bipartite graphs exist only for __k__ = 2 or 3. McCuaig has charac