✦ LIBER ✦

Nonplanar graphs and well-covered cycles

✍ Scribed by R. Bruce Richter

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 116 KB
Volume: 85
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90024-c

No coin nor oath required. For personal study only.

✦ Synopsis

In his talk 'Spanning tees of planar maps' at the 19th Southeastern Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, February 1988), Rosenfeld stated the following conjecture.

Conjecture. Let G be a 2-connected graph and let % be a collection of cycles in G such that:

(i) each edge of G is in exactly two members of %'e; and (ii) for each spanning tree T of G, at least two members of % have all but one edge in T.

Then G is planar.

📜 SIMILAR VOLUMES

Well-covered graphs and extendability

✍ Nathaniel Dean; Jennifer Zito 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 928 KB

Very well covered graphs

✍ O. Favaron 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 481 KB

A gra~h is wen-covered if it has no isolated vertices and all the maximal stable (iadependent) sets have the same cardinality. If fm'thermore this cardinality is equal to ½n, where n is the order of, he graph, the graph is called 'veE¢ well covered'. The class of very well-covered graphs contains in

Subdivisions, parity and well-covered gr

Subdivisions, parity and well-covered graphs

✍ Caro, Yair 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB 👁 2 views

A graph is well-covered if every maximal independent set is maximum. This concept, introduced by Plummer in 1970 (J. Combin. Theory 8 (1970)), is the focal point of much interest and current research. We consider well-covered 2-degenerate graphs and supply a structural (and polynomial time algorithm

Well-Covered Claw-Free Graphs

✍ David Tankus; Michael Tarsi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 336 KB

A characterization of well-covered graph

A characterization of well-covered graphs that contain neither 4- nor 5-cycles

✍ A. Finbow; B. Hartnell; R. J. Nowakowski 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 434 KB 👁 1 views

## Abstract A graph is well covered if every maximal independent set has the same cardinality. A vertex __x__, in a well‐covered graph __G__, is called extendable if __G – {x}__ is well covered and β(__G__) = β(__G – {x}__). If __G__ is a connected, well‐covered graph containing no 4‐ nor 5‐cycles

ModelingK-coteries by well-covered graph

ModelingK-coteries by well-covered graphs

✍ Yamashita, Masafumi; Kameda, Tsunehiko (Tiko) 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 3 views

The concept of k-coterie is useful for achieving k-mutual exclusion in distributed systems. A graph is said to be well covered if any of its maximal independent sets is also maximum. We first show that a graph G is well covered with independence number k if and only if G represents the incidence rel