Distances and Diameters on Iterated Clique Graphs

If G is a graph, its clique graph, k(G), is the intersection graph of all its (maximal) cliques. Iterated clique graphs are then denned recursively by: k0(G) = G and kn (G) = k (kn-1 (G)). We study the relationship between distances in G and distances in kn (G). Then we apply these results to Johnson graphs to give a shorter and simpler proof of Bornstein and Szwarefiterʹs theorem [3]: For each n there exist a graph G such that diam (kn (G)) = diam (G) + n. ledgements to express my thanks to Prof. Victor Neumann-Lara and Prof. Francisco Larriَn for many enjoyable, helpful and motivating discussions on these topics.