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) \leq \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\), \(ESdn{G}\), is the minimum number of edges of \(G\) to be subdivided to get an excellent subdivision graph \(H\). We obtain upper bounds for \(ESdn{G}\). If any one of these upper bounds for \(ESdn{G}\) is attained, then the set of all vertices of \(G\) which are not in any \(\gamma\)-set of \(G\) is an independent set.