A Class of Planar Well-covered Graphs With Girth Four
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 K.) and C5, every 1- well-covered graph contains triangles or 4-cycles. Thus, triangle-free 1 -well- covered graphs necessarily have girth 4. 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1991
- Accession Number
- ADA262424
Entities
People
- Michael R. Pinter
Organizations
- Vanderbilt University