A Class of Well-Covered Graphs With Girth Four
Abstract
A graph is well-covered if every maximal independent set is also a maximum independent set. A 1-well-covered graph G has the additional property that G-v is also well-covered for every point v in G. Thus, the 1-well-covered graphs form a subclass of the well-covered graphs. We examine triangle-free 1- well-covered graphs. Other than C5 and K2, a 1-well-covered graph must contain a triangle or a 4-cycle. Thus, the graphs we consider have girth 4. Two constructions are given which yield infinite families of 1-well-covered graphs with girth 4. These families contain graphs with arbitrarily large independence number.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1991
- Accession Number
- ADA262423
Entities
People
- Michael R. Pinter
Organizations
- Vanderbilt University