Whitney triangulations, local girth and iterated clique graphs

We study the dynamical behaviour of surface triangulations under the iterated application of the clique graph operator k, which transforms each graph G into the intersection graph kG of its (maximal) cliques. A graph G is said to be k-divergent if the sequence of the orders of its iterated clique graphs \V(k(n) G)\ tends to infinity with n. If this is not the case, then G is eventually k-periodic, or k-bounded. k(n)G congruent to k(m)G for some m > n. The case in which G is the underlying graph of a regular triangulation of some closed surface has been previously studied under the additional (Whitney) hypothesis that every triangle of G is a face of the triangulation: if G is regular of degree d, it is known that G is k-bounded for d = 3 and k-divergent for d = 4,5,6. We will show that G is k-bounded for all d greater than or equal to 7, thus completing the study of the regular case. Our proof works in the more general setting of graphs with local girth at least 7. As a consequence we obtain also the k-boundedness of the underlying graph G of any triangulation of a compact surface (with or without border) provided that any triangle of G is a face of the triangulation and that the minimum degree of the interior vertices of G is at least 7. (C) 2002 Published by Elsevier Science B.V.