Distances and diameters on iterated clique graphs Original Research Article

If G is a graph, its clique graph, K(G), is the intersection graph of all its (maximal) cliques. Iterated clique graphs are then defined 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 Szwarcfiterʹs theorem: For each n there exists a graph G such that diam(Kn(G))=diam(G)+n. In the way, a new family of graphs with increasing diameters under the clique operator is shown.