Accession Number:

ADA261945

Title:

Planar Strongly Well-Covered Graphs

Descriptive Note:

Corporate Author:

VANDERBILT UNIV NASHVILLE TN

Personal Author(s):

Report Date:

1991-01-01

Pagination or Media Count:

12.0

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.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE