✦ LIBER ✦

On n-connected graphs

✍ Scribed by Branko Grünbaum

Publisher: John Wiley and Sons
Year: 1969
Tongue: English
Weight: 183 KB
Volume: 39
Category: Article
ISSN: 0025-584X
DOI: 10.1002/mana.19690390411

No coin nor oath required. For personal study only.

✦ Synopsis

The main aim of the present note is the proof of a variant of the MENGER-WHITNEY theorem on n-connected graphs (Theorem 1 below). While the result itself is well known (being, for example, a special case of the theorem of MENGER mentioned in Remark I), two of its aspects deserve attention. First, it is the core of many other combinatorial results of the mininiummaximum type (see the Remarks). Besides, its proof seems to be simpler than the published proofs of theMENGER-WHITNEY theorem or related results.

We shall consider only graphs without 1-or 2-circuits; it is well known that this does not significantly restrict the validity of the results. All graphs will be assumed finite. If G is a graph and N a set of nodes of G, we denote by G -N the graph obtained from G by omitting the nodes in N and the edges incident with them. A set N of nodes of G disconnects G between the nodes x,, , x1 if and only if G -N contains no path with endpoints x,, and xi.

📜 SIMILAR VOLUMES

On Minimally (n, λ)-Connected Graphs

✍ Atsushi Kaneko; Katsuhiro Ota 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 128 KB

A graph G is (n, \*)-connected if it satisfies the following conditions: (1) |V(G)| n+1; (2) for any subset S V(G) and any subset L E(G) with \* |S| +|L| <n\*, G&S&L is connected. The (n, \*)-connectivity is a common extension of both the vertex-connectivity and the edge-connectivity. An (n, 1)-conn

On k-con-Critically n-Connected Graphs

✍ W. Mader 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 221 KB

We prove that every n-connected graph G of sufficiently large order contains a connected graph H on four vertices such that G À V ðH Þ is ðn À 3Þ-connected. This had been conjectured in Mader (High connectivity keeping sets in n-connected graphs, Combinatorica, to appear). Furthermore, we prove uppe

Fragments in kcritical n-connected graph

Fragments in kcritical n-connected graphs

✍ Su Jianji 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

## Abstract Madar conjectured that every __k__‐critical __n__‐connected non‐complete graph __G__ has (2__k__ + 2) pairwise disjoint fragments. We show that Mader's conjecture holds if the order of __G__ is greater than (__k__ + 2)__n__. From this, it implies that two other conjectures on __k__‐crit

On Hamiltonian-connected regular graphs

✍ Ioan Tomescu 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 360 KB

In this paper it is shown that any rn-regular graph of order 2rn (rn 3 3), not isomorphic to K, , , , or of order 2rn + 1 (rn even, rn 3 4), is Hamiltonian connected, which extends a previous result of Nash-Williams. As a corollary, it is derived that any such graph contains at least rn Hamiltonian

Proof of Mader's conjecture on k-critica

Proof of Mader's conjecture on k-critical n-connected graphs

✍ Su Jianji 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB 👁 1 views

## Abstract Mader conjectured that every __k__‐critical __n__‐connected noncomplete graph __G__ has __2k__ + 2 pairwise disjoint fragments. The author in 9 proved that the conjecture holds if the order of __G__ is greater than (__k__ + 2)__n__. Now we settle this conjecture completely. © 2004 Wiley

Fragments in 2-Critically n-Connected Gr

Fragments in 2-Critically n-Connected Graphs

✍ J.J. Su 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 428 KB

Mader conjectured that every non-complete \(k\)-critically \(n\)-connected graph has \((2 k+2)\) pairwise disjoint fragments. The conjecture was verified by Mader for \(k=1\). In this paper, we prove that this conjecture holds also for \(k=2\). 1993 Academic Press. Inc.