Iterated Clique Graphs of Triangulations



The clique graph k(G) of a graph G has its vertices the maximal cliques of G, and its edges joining two maximal cliques sharing a common vertex. Define k^2(G) = k(k(G)), and define k^n(G) similarly; these are called the iterated clique graphs. There are two possibilities: 1) the order of k^n(G) approaches infinity as n approaches infinity, or 2) k^n(G) is eventually a periodic sequence of graphs (the latter includes the possibility that the iterated clique graph is eventually K_1). In the former case we call the graph clique divergent.

Iterated clique graphs are particularly interesting for graphs that triangulate some surface. More strongly, a Whitney triangulation is an embedding of a graph in a surface such that 1) every face is a triangle, and 2) every triangle is a face. Equivalently, the (open) neighborhood of each vertex is a cycle, or equivalently, the graph underlying the triangulation is 4-connected (except for K_4) and any non-contractible cycle is of length at least 4.

Conjecture: [LNP1] Any Whitney triangulaton of the sphere (except K_4) is clique divergent.

It is known [LNP1] that all Whitney triangulations of minimum degree 7 or greater are not clique divergent, in particular, k^3(G)=k(G). In contrast, [LN1,LN2] all 6-regular Whitney triangulations (necessarily of the torus or the Klein bottle) are clique divergent. The icosahedron is the unique 5-regular Whitney triangulation, and it is clique divergent [P]. The unique regular 4-regular Whitney triangulation is the octahedron, which is clique divergent [E,N].

Interested readers should also see [LNP2] and [LNP3], which contain related results. Copies of these papers are available at http://xamanek.izt.uam.mx/map.  

References:

[E] F. Escalante, Uber iteriete clique-graphen, Abh. Math. Sem. Univ. Hamburg 39 (1973) 58-68

[LNP1] F. Larrion, V. Neumann-Lara, and M.A. Pizana,Whitney triangulations, local girth and iterated clique graphs, Discrete Math. 258 (2002)123-135.

[LNP2] F. Larrion, V. Neumann-Lara, and M.A. Pizana, On the homotopy type of clique graphs, J. of the Brazilian Comp. Soc. 7-3 (2002) 69-73.

[LNP3] F. Larrion, V. Neumann-Lara, and M.A. Pizana, Convergent surface triangulations, Mat. Contemp. 25 (2003) 135-143.

[P] M.A. Pizana, The icosahedron is clique-divergent, Discrete Math. 262 (2003) 229-239.

[LN1] F. Larrion and V. Neumann-Lara, Clique divergent graphs with unbounded sequence of diameters, Discrete Math. 197-198 (1999) 491-501

[LN2] F. Larrion and V. Neumann-Lara, Locally C_6 graphs are clique divergent, Discrete Math. 215 (2000) 159-170

[N]  V. Neumann-Lara, On clique-divergent graphs, in Problemes Combinatoires et Theorie des Graphes (Colloques internationaux CNRS, 260) Paris, Editions du CNRS (1978) 313-315.


Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu

December 2003