✦ LIBER ✦

Very well covered graphs

✍ Scribed by O. Favaron

Publisher: Elsevier Science
Year: 1982
Tongue: English
Weight: 481 KB
Volume: 42
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(82)90215-1

No coin nor oath required. For personal study only.

✦ Synopsis

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 particular the bipartite well-covered graphs studied by Ravindra. In th'h article, we characte~ ize the very well covered-graphs and give some of ~heir properties. U, g'ar~he est dit bien couvert s'il est sans sommets isol6s et si tous ses ensembles stables (ind6pendants) maximaux ont la mdme cardinalit6. Si, de plus, cette cardinal~t~ est ~n, ot~ n d6sie, ne le nombre de sommets du graphe, le graphe est appel6 'tr~s bien couveW. La classe des graphes t~es bien couverts contient en particulier les graphes bipartis bien couverts 6tudi~s par Rav~ndra D~as cet article, nous caract~risons los grapbes tr~s bien converts et ~t~blissort,, cel'.aine.~ Ce leurs propri6t6s.

O. lntrc~d~c~jan

In whai fot'iows, G will denote a simple undirected ga-aph G(V, E) of order n--Ivl.

A stable !9. ind~p~endent) ~et S is a set of nonadjacent vertices. ~' (resp. t~) wLll denote the m~nimtlm (resp. maximum) cardinality of a maximal stable set. D is a dominating set if and only if every point of V-D is adjacent to a point of D. W.~ v,,ilt denote by ~/ (resp. F) the minimum (resp. maximum) cardinality of a minim:d dominating set.

Let u~ c!e~ote by F(x) the set of vertices adjacent to x and, more generally, F(A) = ~.~ F(x) for A m V. A vertex x of A is said to be redundant in A ~7 x U F(x)~ U(A-x)U {A-x}. A set I of vertices containing no rednndagd v~rtex is call,~d firedundant. Equivalently, I is Jrredundant ff eve~, point of I either is adjacent to no other point of/, or is adjacent to a point of V-I itself adjacent to no other point of L We will denote by ir (resp. IR) the minimum (resp. maximum) cardinality of a maximal irredundant set.

The different parameters a, a', T, F, ir, IR have already been studied in many articles (see [2] for example). In particular we have the following relations,:

📜 SIMILAR VOLUMES

Well-Covered Claw-Free Graphs

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

Well-covered graphs and extendability

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

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

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

Nonplanar graphs and well-covered cycles

✍ R. Bruce Richter 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 116 KB

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)

Complexity results for well-covered grap

Complexity results for well-covered graphs

✍ Ramesh S. Sankaranarayana; Lorna K. Stewart 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 740 KB

## Abstract A graph with __n__ vertices is well covered if every maximal independent set is a maximum independent set and very well covered if every maximal independent set has size __n__/2. In this work, we study these graphs from an algorithmic complexity point of view. We show that well‐covered