IRREDUNDANCE IN INFLATED GRAPHS

The inflation G(I) of a graph G(I) with n(G) vertices and m(G) edges i s obtained by replacing every vertex of degree d of G by a clique K-d. We study the lower and upper irredundance parameters ir and IR of an inflation. We prove in particular that if gamma denotes the domination number of a graph, gamma(GI) -ir(G(I)) can be arbitrarily large, IR(G (I)) less than or equal to m(G) and IR(G(I)) less than or equal to n(2 )(G)/4. These results disprove a conjecture of Dunbar and Haynes (Cong r. Num, 118 (1996), 143-154) and answer another open question. (C) 199 8 John Wiley & Sons, Inc.