✦ LIBER ✦

Matching cutsets in graphs

✍ Scribed by Augustine M. Moshi

Publisher: John Wiley and Sons
Year: 1989
Tongue: English
Weight: 504 KB
Volume: 13
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190130502

No coin nor oath required. For personal study only.

✦ Synopsis

Let G = ( Y E ) be an undirected graph. A subset F of E is a matching cutset of G if no two edges of Fare incident with the same point, and G-F has more components than G. ChGatal [2] proved that it is NP-complete to recognize graphs with a matching cutset even if the input is restricted to graphs with maximum degree 4. We prove the following: (a) Every connected graph with maximum degree 1 3 and on more than 7 points has a matching cutset. (In particular, there are precisely two connected cubic graphs without a matching cutset). (b) Line graphs with a matching cutset can be recognized in O( IE 1) time. (c) Graphs without a chordless circuit of length 5 or more that have a matching cutset can be recognized in O( IVI [El 3, time.

📜 SIMILAR VOLUMES

Small cutsets in quasiminimal Cayley gra

Small cutsets in quasiminimal Cayley graphs

✍ Y.O. Hamidoune; A.S. Lladó; O. Serra 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 586 KB

We continue the recent study carried out by several authors on the cut sets in Cayley graphs with respect to quasiminimal generating sets. We improve the known results on these questions. The application of our main theorem to symmetric Cayley graphs on minimal generating sets leads to the followin

Star-cutsets and perfect graphs

✍ V Chvátal 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 822 KB

Matchings, cutsets, and chain partitions

Matchings, cutsets, and chain partitions in graded posets

✍ Jerrold R. Griggs 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 612 KB

Kernels in graphs with a clique-cutset

✍ Henry Jacob 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 138 KB

We consider graphs that have a clique-cutset, and we show that this property preserves the existence of a kernel in a certain sense. We consider finite directed graphs that do not have multiple arcs or loops, but there may be symmetric arcs between some pairs of vertices. Let G = (V, A) be a direct

Disjoint clique cutsets in graphs withou

Disjoint clique cutsets in graphs without long holes

✍ Elaine M. Eschen; Chính T. Hoàng; Mark D. T. Petrick; R. Sritharan 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB

## Abstract A biclique cutset is a cutset that induces the disjoint union of two cliques. A hole is an induced cycle with at least five vertices. A graph is biclique separable if it has no holes and each induced subgraph that is not a clique contains a clique cutset or a biclique cutset. The class

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