Accession Number : ADA261945


Title :   Planar Strongly Well-Covered Graphs


Corporate Author : VANDERBILT UNIV NASHVILLE TN


Personal Author(s) : Pinter, Michael R


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a261945.pdf


Report Date : Jan 1991


Pagination or Media Count : 12


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.


Descriptors :   *GRAPHS , EDGES , THEORY , INCLUSIONS , THEOREMS


Subject Categories : Numerical Mathematics


Distribution Statement : APPROVED FOR PUBLIC RELEASE