Planar Regular One-Well-Covered Graphs
Michael P. Pinter · 1991
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.