✦ LIBER ✦

Extremal 3-connected graphs

✍ Scribed by Stephen C. Locke

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 686 KB
Volume: 68
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90117-3

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a 3-connected graph with minimum degree at least d and at least 2d vertices. For any three distinct vertices X, y, z there is a path from x to z through y and having length at least M -2. In this paper, we characterize those graphs for which no such path has length exceeding 2d -2.

I.

All graphs considered in this paper are simple. For basic graph-theoretic terminology, we refer the reader to [2].

The following was proved in [4,5].

Let G be a 3-connected graph with minimum decree c2t least d and at least 2d -1 vertices, for some positive integer d. Then, for any three vertices x, y, and z in G, there is an (x9 z)-path of length at least 2d -2 which contains y.

📜 SIMILAR VOLUMES

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 connectivity and vulnerability

Extremal connectivity and vulnerability in graphs

✍ Lynne L. Doty 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 290 KB

On the extremal number of edges in hamil

On the extremal number of edges in hamiltonian connected graphs

✍ Tung-Yang Ho; Cheng-Kuan Lin; Jimmy J.M. Tan; D. Frank Hsu; Lih-Hsing Hsu 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 421 KB

a b s t r a c t Assume that n and δ are positive integers with 3 ≤ δ < n. Let hc(n, δ) be the minimum number of edges required to guarantee an n-vertex graph G with minimum degree δ(G) ≥ δ to be hamiltonian connected.

Cyclability of 3-connected graphs

✍ Amel Harkat-Benhamdine; Hao Li; Feng Tian 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB 👁 1 views

Counting labelled 3-connected graphs

✍ Nicholas Wormald 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 62 KB

Minimum 3-geodetically connected graphs

✍ Martina Bosı́ková 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 793 KB

A graph G is k-geodetically connected (k-GC) if it is connected and the removal of at least k vertices is required to increase the distance between at least one pair of vertices or reduce G to a single vertex. We completely characterize the class of minimum 3-GC graphs that have the fewest edges for