A Note on Excellent Graphs

Abstract

A graph $G$ is said to be excellent if, given any vertex $x$ of $G$, there is a $\gamma$-set of $G$ containing $x$. It is known that any non-excellent graph can be imbedded in an excellent graph. For example, for every graph $G$, its corona $G\circ K$ is excellent, but the difference $\gamma (G\circ K)–\gamma (G)$ may be high. In this paper, we give a construction to imbed a non-excellent graph $G$ in an excellent graph $H$ such that $\gamma (H)\le \gamma (G)+2$. We also show that, given a non-excellent graph $G$, there is a subdivision of $G$ which is excellent. The excellent subdivision number of a graph $G$, $ESdnG$, is the minimum number of edges of $G$ to be subdivided to get an excellent subdivision graph $H$. We obtain upper bounds for $ESdnG$. If any one of these upper bounds for $ESdnG$ is attained, then the set of all vertices of $G$ which are not in any $\gamma$-set of $G$ is an independent set.