Planar Strongly Well-Covered Graphs
VANDERBILT UNIV NASHVILLE TN
Pagination or Media Count:
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.
- Numerical Mathematics