✦ LIBER ✦

Induced paths in 5-connected graphs

✍ Scribed by Matthias Kriesell

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 75 KB
Volume: 36
Category: Article
ISSN: 0364-9024
DOI: 10.1002/1097-0118(200101)36:1<52::aid-jgt5>3.0.co;2-n

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Light paths in 4-connected graphs in the

Light paths in 4-connected graphs in the plane and other surfaces

✍ Bojan Mohar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB

On paths in planar graphs

✍ Sanders, Daniel P. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 93 KB 👁 1 views

This paper generalizes a theorem of Thomassen on paths in planar graphs. As a corollary, it is shown that every 4-connected planar graph has a Hamilton path between any two specified vertices x, y and containing any specified edge other than xy.

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

Some results on graphs without long indu

Some results on graphs without long induced paths

✍ Dong, Jinquan 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB

Let I(t) be the set of integers with the property that in every Pt-free connected graph G, the i-center C,(G) induces a connected subgraph. What is the minimum element of /(t)? In this paper, we prove that this minimum is [2t/3] -1 if t = 0 or Z(mod3) and is [ 2 t / 3 ] otherwise. Furthermore, as co

Extremal graphs in connectivity augmenta

Extremal graphs in connectivity augmentation

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

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

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