✦ LIBER ✦

A Characterization of Well Covered Graphs of Girth 5 or Greater

✍ Scribed by A. Finbow; B. Hartnell; R.J. Nowakowski

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 998 KB
Volume: 57
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1993.1005

No coin nor oath required. For personal study only.

✦ Synopsis

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 (\beta(G)=\beta(G-{x})). If (G) is a connected, well covered graph of girth (\geqslant 5) and (G) contains an extendable vertex then (G) is the disjoint union of edges and 5 -cycles together with a restricted set of edges joining these subgraphs. There are only six connected, well covered graphs of girth (\geqslant 5) which do not contain an extendable vertex. 1993 Academic Press. Inc.

📜 SIMILAR VOLUMES

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

A class of planar well-covered graphs wi

A class of planar well-covered graphs with girth four

✍ Michael R. Pinter 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 616 KB

## Abstract A well‐covered graph is a graph in which every maximal independent set is a maximum independent set; Plummer introduced the concept in a 1970 paper. The notion of a 1‐well‐covered graph was introduced by Staples in her 1975 dissertation: a well‐covered graph __G__ is 1‐well‐covered if a

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

A non-covering graph of girth six

✍ Oliver Pretzel 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 228 KB

We construct a graph of girth 6 that cannot be oriented as the diagram of an ordered set and discuss the reasons why this particular construction cannot be extended to produce examples of larger girth. The problem of characterizing graphs that can be oriented as diagrams of ordered sets (or coverin

A smallest graph of girth 5 and valency

A smallest graph of girth 5 and valency 6

✍ M O'Keefe; Pak-Ken Wong 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 309 KB

A characterization of graphs of girth ei

A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets

✍ A. Finbow; B. Hartnell; C. Whitehead 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 1003 KB

In 1970, Plummer introduced the notion of a well-covered graph as one in which every maximal independent set is a maximum. Here, we study graphs in which there are exactly two sizes of maximal independent sets. A characterization of such graphs is obtained for graphs of girth eight or more.