𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Extremal graphs in connectivity augmentation

✍ Scribed by Jord�n, Tibor

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
245 KB
Volume
31
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

For undirected vertex-connectivity we determine A(n, k, 1) for all values of n and k. We also describe the graphs that attain the extremal values.

📜 SIMILAR VOLUMES

Induced paths in 5-connected graphs
Induced paths in 5-connected graphs
✍ Matthias Kriesell 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 75 KB 👁 1 views

We show that between any two vertices of a 5-connected graph there exists an induced path whose vertices can be removed such that the remaining graph is 2-connected.

Connected subgraphs with small degree su
Connected subgraphs with small degree sums in 3-connected planar graphs
✍ Enomoto, Hikoe; Ota, Katsuhiro 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we sh

Matching extension in the powers ofn-con
Matching extension in the powers ofn-connected graphs
✍ Walcher, Kara Lee 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB

Let G be a graph on p vertices. Then for a positive integer n, G is said to be n-extendible if (i) TI < p / 2 , iii) G has a set of n independent edges, and (iii) every such set is contained in a perfect matching of G. In this paper we will show that if p is even and G is TIconnected, then Gk is ([$

Toughness and longest cycles in 2-connec
Toughness and longest cycles in 2-connected planar graphs
✍ B�hme, T.; Broersma, H. J.; Veldman, H. J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 390 KB 👁 1 views

Let G be a planar graph on n vertices, let c(G) denote the length of a longest cycle of G, and let w(G) denote the number of components of G. By a well-known theorem of Tutte, c(G) = n (i.e., G is hamiltonian) if G is 4-connected. Recently, Jackson and Wormald showed that c(G) 2 ona for some positiv

Long paths through four vertices in a 2-
Long paths through four vertices in a 2-connected graph
✍ Barovich, Mark V. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 1 views

Let G be a 2-connected graph, let u and v be distinct vertices in V (G), and let X be a set of at most four vertices lying on a common (u

Extremal graphs of diameter two and give
Extremal graphs of diameter two and given maximum degree, embeddable in a fixed surface
✍ Knor, Martin; ?ir�?, Jozef 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 1 views

It is known that for each d there exists a graph of diameter two and maximum degree d which has at least (d/2) (d + 2)/2 vertices. In contrast with this, we prove that for every surface S there is a constant d S such that each graph of diameter two and maximum degree d ≥ d S , which is embeddable in