Diameters of iterated clique graphs of chordal graphs

Abstract

Abstract The clique graph K ( G ) of a graph is the intersection graph of maximal cliques of G. The iterated clique graph K n ( G ) is inductively defined as K (K n−1 ( G )) and K 1 ( G ) = K ( G ). Let the diameter diam( G ) be the greatest distance between all pairs of vertices of G. We show that diam( K n ( G )) = diam( G ) — n if G is a connected chordal graph and n ≤ diam( G ). This generalizes a similar result for time graphs by Bruce Hedman.