✦ LIBER ✦

On k-con-Critically n-Connected Graphs

✍ Scribed by W. Mader

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 221 KB
Volume: 86
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2002.2129

No coin nor oath required. For personal study only.

✦ Synopsis

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 upper bounds for the order of all n-connected graphs of criticality 3, 4, and 5.

📜 SIMILAR VOLUMES

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.

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

On n-connected graphs

✍ Branko Grünbaum 📂 Article 📅 1969 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB

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

Maximam critical n-edge connected graph

📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB

Characterization of maximum critically 2

Characterization of maximum critically 2-connected graphs

✍ R. C. Entringer 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 346 KB

## Abstract A graph __G__ is critically 2‐connected if __G__ is 2‐connected but, for any point __p__ of __G, G — p__ is not 2‐connected. Critically 2‐connected graphs on __n__ points that have the maximum number of lines are characterized and shown to be unique for __n__ ⩾ 3, __n__ ≠ 11.

On critically connected digraphs

✍ W. Mader 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 481 KB