Irredundance in inflated graphs
Odile Favaron · Journal of Graph Theory · 1998
The inflation GI of a graph G with n(G) vertices and m(G) edges is obtained by replacing every vertex of degree d of G by a clique Kd. We study the lower and upper irredundance parameters ir and IR of an inflation. We prove in particular that if γ denotes the domination number of a graph, γ(GI) − ir(GI) can be arbitrarily large, IR(GI) ≤ m(G) and IR(GI) ≤ n2(G)/4. These results disprove a conjecture of Dunbar and Haynes (Congr. Num. 118 (1996), 143–154) and answer another open question. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 97–104, 1998