✦ LIBER ✦

On stable cutsets in line graphs

✍ Scribed by Van Bang Le; Bert Randerath

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 253 KB
Volume: 301
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(03)00048-3

No coin nor oath required. For personal study only.

✦ Synopsis

We answer a question of Brandst adt et al. by showing that deciding whether a line graph with maximum degree 5 has a stable cutset is NP-complete. Conversely, the existence of a stable cutset in a line graph with maximum degree at most 4 can be decided e ciently. The proof of our NP-completeness result is based on a reÿnement on a result due to ChvÃ atal that recognizing decomposable graphs with maximum degree 4 is an NP-complete problem. Here, a graph is decomposable if its vertices can be colored red and blue in such a way that each color appears on at least one vertex but each vertex v has at most one neighbor having a di erent color from v. We also discuss some open problems on stable cutsets.

📜 SIMILAR VOLUMES

Matching cutsets in graphs

✍ Augustine M. Moshi 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 504 KB

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 w

Galaxy cutsets in graphs

✍ Nicolas Sonnerat; Adrian Vetta 📂 Article 📅 2009 🏛 Springer US 🌐 English ⚖ 363 KB

Cutsets in ak-connected graph

✍ D. V. Karpov 📂 Article 📅 2007 🏛 Springer US 🌐 English ⚖ 243 KB

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

On slim graphs, even pairs, and star-cut

On slim graphs, even pairs, and star-cutsets

✍ Chính T. Hoàng; Frédéric Maffray 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 724 KB

Hoang, C.T. and F. Maffray, On slim graphs, even pairs, and star-cutsets, Discrete Mathematics 105 (1992) 93-102. Meyniel proved that a graph G is perfect if every odd cycle of G with at least five vertices has at least two chords. A slim graph is any graph obtained from a Meyniel graph by removing

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