Accession Number:

ADA261946

Title:

Planar Regular One-Well-Covered Graphs

Descriptive Note:

Corporate Author:

VANDERBILT UNIV NASHVILLE TN

Personal Author(s):

Report Date:

1991-01-01

Pagination or Media Count:

31.0

Abstract:

An independent set in a graph is a subset of vertices with the property that no two of the vertices are joined by an edge, and a maximum independent set in a graph is an independent set of the largest possible size. A graph is called well-covered if every independent set that is maximal with respect to set inclusion is also a maximum independent set. If G is a well- covered graph and G - v is also well-covered for all vertices v in G, then we say G is 1-well-covered. By making use of a characterization of cubic well- covered graphs, it is straightforward to determination all cubic 1-well-covered graphs. Since there is no known characterization of k-regular well-covered graphs for k 4, it is more difficult to determine the k-regular 1 -well- covered graphs for k 4. The main result in this regard is the determination of all 3-connected 4-regular planar 1-well-covered graphs.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE