On $\alpha$-excellent graphs

Abstract

A graph $G$ is $\alpha$-excellent if every vertex of $G$ is contained in some maximum independent set of $G$. In this paper, we characterize $\alpha$-excellent bipartite graphs, $\alpha$-excellent unicyclic graphs, $\alpha$-excellent simplicial graphs, $\alpha$-excellent chordal graphs, $\alpha$-excellent block graphs, and we show that every generalized Petersen graph is $\alpha$-excellent.

15 pages, 4 figures