ITERATED CLIQUE GRAPHS WITH INCREASING DIAMETERS

A simple argument by Hedman shows that the diameter of a clique graph G differs by at most one from that of K(G), its clique graph. Hedman d escribed examples of a graph G such that diam(K(G)) = diam(G) + 1 and asked in general about the existence of graphs such that diam(KZ(G)) = diam(G) + i. Examples satisfying this equality for i = 2 have been de scribed by Peyrat, Rall, and Slater and independently by Balakrishnan and Pauiraja. The authors of the former work also solved the case i = 3 and i = 4 and conjectured that such graphs exist for every positive integer i. The cases i greater than or equal to 5 remained open. In th e present article, we prove their conjecture. For each positive intege r i, we describe a family of graphs G such that diam(K-i(G)) = diam(G) + i. (C) 1998 John Wiley & Sons, Inc.