✦ LIBER ✦

On some subclasses of well-covered graphs

✍ Scribed by Jo Ann W. Staples

Publisher: John Wiley and Sons
Year: 1979
Tongue: English
Weight: 367 KB
Volume: 3
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190030211

No coin nor oath required. For personal study only.

✦ Synopsis

A set of points in a graph is independent if no two points in the set are adjacent. A graph is well covered if every maximal independent set is a maximum independent set or, equivalently, if every independent set is contained in a maximum independent set. The well-covered graphs are classified by the W,, property: For a positive integer n, a graph G belongs to class W,, if \ V ( G ) I r n and any n disjoint independent sets are contained in n disjoint maximum independent sets. Constructions are presented that show how to build infinite families of W,, graphs containing arbitrarily large independent sets. A characterization of W, graphs in terms of well-covered subgraphs is given, a s well a s bounds for the size of a maximum independent set and the minimum and maximum degrees of points in W, graphs.

📜 SIMILAR VOLUMES

On some subclasses of P-matrices

✍ Hou-Biao Li; Ting-Zhu Huang; Hong Li 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract A matrix with positive row sums and all its off‐diagonal elements bounded above by their corresponding row averages is called a __B__‐matrix by J. M. Peña in References (__SIAM J. Matrix Anal. Appl.__ 2001; **22**:1027–1037) and (__Numer. Math.__ 2003; **95**:337–345). In this paper, it

On Generalizations of Matching-covered G

On Generalizations of Matching-covered Graphs

✍ Zoltán Szigeti 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 184 KB

A characterization of Zm-well-covered gr

A characterization of Zm-well-covered graphs of girth 6 or more

✍ Caro, Y.; Hartnell, B. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 2 views

The class of Z m -well-covered graphs, those in which the cardinality of every maximal independent subset of vertices is congruent to the same number modulo m, contains the well-covered graphs as well as parity graphs. Here we consider such graphs, where there is no small cycle present and obtain a

The Structure of Well-Covered Graphs and

The Structure of Well-Covered Graphs and the Complexity of Their Recognition Problems

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

A graph is well-covered if all its maximal independent sets are of the same cardinality. Deciding whether a given graph is well-covered is known to be NP-hard in general, and solvable in polynomial time, if the input is restricted to certain families of graphs. We present here a simple structural ch

Five Cycle Double Covers of Some Cubic G

Five Cycle Double Covers of Some Cubic Graphs

✍ A. Huck; M. Kochol 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 257 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