✦ LIBER ✦

The connectivity of minimal imperfect graphs

✍ Scribed by Seb�, Andr�s

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 535 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199609)23:1<77::aid-jgt9>3.0.co;2-h

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that partitionable graphs are 2w -2-connected, that this bound is sharp, and prove some structural properties of cutsets of cardinality 2w -2. The proof of the connectivity result is a simple linear algebraic proof.

📜 SIMILAR VOLUMES

On minimal imperfect graphs with circula

On minimal imperfect graphs with circular symmetry

✍ Bacs�, G�bor; Boros, Endre; Gurvich, Vladimir; Maffray, Fr�d�ric; Preissmann, My 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 293 KB

Results of Lovász and Padberg entail that the class of so-called partitionable graphs contains all the potential counterexamples to Berge's famous Strong Perfect Graph Conjecture, which asserts that the only minimal imperfect graphs are the odd chordless cycles with at least five vertices (''odd hol

About Skew Partitions in Minimal Imperfe

About Skew Partitions in Minimal Imperfect Graphs

✍ F. Roussel; P. Rubio 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 188 KB

V. Chva tal conjectured in 1985 that a minimal imperfect graph G cannot have a skew cutset (i.e., a cutset S decomposable into disjoint sets A and B joined by all possible edges). We prove here the conjecture in the particular case where at least one of A and B is a stable set. 2001 Elsevier Science

Minimally 2-edge connected graphs

✍ G. Chaty; M. Chein 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 338 KB

## Abstract A constructive characterization of minimally 2‐edge connected graphs, similar to those of Dirac for minimally 2‐connected graphs is given.

Minimal k-arc connected graphs

✍ D. R. Fulkerson; L. S. Shapley 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 364 KB

Complete Multi-partite Cutsets in Minima

Complete Multi-partite Cutsets in Minimal Imperfect Graphs

✍ G. Cornuejols; B. Reed 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 316 KB

We show that a minimal imperfect graph \(G\) cannot contain a cutset \(C\) which induces a complete multi-partite graph unless \(C\) is a stable set and \(G\) is an odd hole. This generalizes a result of Tucker, who proved that the only minimal imperfect graphs containing stable cutsets are the odd

Minimally (k, k)-edge-connected graphs

✍ Kamal Hennayake; Hong-Jian Lai; Deying Li; Jingzhong Mao 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB 👁 1 views

## Abstract For an integer __l__ > 1, the __l__‐edge‐connectivity of a connected graph with at least __l__ vertices is the smallest number of edges whose removal results in a graph with __l__ components. A connected graph __G__ is (__k__, __l__)‐edge‐connected if the __l__‐edge‐connectivity of __G_