Header menu link for other important links
X
A note on excellent graphs
N. Sridharan,
Published in
2006
Volume: 78
   
Pages: 267 - 276
Abstract
A graph G is said to be excellent if given any vertex x of G, there is a γ - 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 o K1 is excellent, but the difference γ(G o K1) - γ (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 γ(H) ≤ γ(G) + 2. We also show that given a non - excellent graph G, there is 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 γ - set of G is an independent set.
About the journal
JournalArs Combinatoria
ISSN03817032