A class of planar well‐covered graphs with girth four
Author:
- 1 January 1995
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 19 (1) , 69-81
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 and only if G ‐ v is also well covered for every point v in G. Except for K2 and C5, every 1‐well‐covered graph contains triangles or 4‐cycles. We show that all planar 1‐well‐covered graphs of girth 4 belong to a specific infinite family, and we give a characterization of this family. © 1995 John Wiley & Sons, Inc.Keywords
This publication has 7 references indexed in Scilit:
- A Characterization of Well Covered Graphs of Girth 5 or GreaterJournal of Combinatorial Theory, Series B, 1993
- A Class of Well-Covered Graphs With Girth Four1991
- Very well covered graphsDiscrete Mathematics, 1982
- On some subclasses of well‐covered graphsJournal of Graph Theory, 1979
- Perfect product graphsDiscrete Mathematics, 1977
- Graph Theory with Applications1976
- Some covering concepts in graphsJournal of Combinatorial Theory, 1970