**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.,

Send comments to *dan.archdeacon@uvm.edu*

December 2003