𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The k-Critical 2k-Connected Graphs for k∈{3, 4}

✍ Scribed by Matthias Kriesell

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
180 KB
Volume
78
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

A noncomplete graph G is called an (n, k)-graph if it is n-connected and G&X is not (n&|X | +1)-connected for any X V(G) with |X | k. Mader conjectured that for k 3 the graph K 2k+2 -(1-factor) is the unique (2k, k)-graph. We settle this conjecture for k 4.

📜 SIMILAR VOLUMES

On k-con-Critically n-Connected Graphs
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

A necessary and sufficient condition for
A necessary and sufficient condition for connected, locally k-connected k1,3-free graphs to be k-hamiltonian
✍ Zhou Huai-Lu 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB 👁 2 views

We prove the following conjecture of Broersma and Veldman: A connected, locally k-connected K,,-free graph is k-hamiltonian if and only if it is (k + 2)-connected ( k L 1). We use [ 11 for basic terminology and notation, and consider simple graphs only. Let G be a graph. By V(G) and E(G) we denote,

Connected, locally 2-connected, K1,3-fre
Connected, locally 2-connected, K1,3-free graphs are panconnected
✍ S. V. Kanetkar; P. R. Rao 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 1 views

## Abstract A graph __G__ is locally __n__‐connected, __n__ ≥ 1, if the subgraph induced by the neighborhood of each vertex is __n__‐connected. We prove that every connected, locally 2‐connected graph containing no induced subgraph isomorphic to __K__~1,3~ is panconnected.

The symmetric (2k, k)-graphs
The symmetric (2k, k)-graphs
✍ Matthias Kriesell 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB 👁 1 views
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