Planar Strongly Well-Covered Graphs
Abstract
Plummer introduced the concept of a well-covered graph in 1970. A graph is well-covered if every maximal independent set (with respect to set inclusion) in the graph is also a maximum independent set. Various subclasses of well-covered graphs have been studied. We consider the subclass which we call strongly well-covered graphs. A strongly well-covered graph G is a well-covered graph with the additional property that G-e is also well-covered for every edge e in G. By making use of (1) structural characteristics of strongly well-covered graphs and (2) the theory of Euler contributions (for planar graphs), we show that there are only four planar strongly well-covered graphs.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1991
- Accession Number
- ADA261945
Entities
People
- Michael R. Pinter
Organizations
- Vanderbilt University