Clique Dynamics of Finite or Infinite Locally Cyclic Graphs with δ ≥ 6

We prove that the clique graph operator k is divergent on a (not necessarily finite) locally cyclic graph G  with minimum degree δ ≥ 6 if and only if the universal triangular cover of G contains arbitrarily large triangular-shaped subgraphs. For finite G, this is equivalent to G being 6-regular.

A graph is called locally cyclic if the open neighbourhood N_G(v) of each vertex v induces a cycle. The clique graph kG of a graph G has the maximal complete subgraphs of G as its vertices and its edges are those pairs with non-empty intersection. The (n+1)-st iterated clique graph is recursively defined as the clique graph of the n-th iterated clique graph. If all iterated clique graphs of G are non-isomorphic, the graph G is called k-divergent; otherwise, it is k-convergent.

While it has been shown for finite locally cyclic graphs that those with minimum degree δ ≥ 7 are k-convergent while the 6-regular ones are k-divergent, we obtain a full characterisation of k-convergent locally cyclic graphs with minimum degree δ ≥ 6.

We start by showing that a k-convergent connected graph has a k-convergent universal triangular cover. Conversely, we give a sufficient condition under which the clique convergence of the universal triangular cover of a graph implies the clique convergence of the graph itself.

Locally cyclic graphs with minimum degree δ ≥ 6 which are triangularly simply connected are their own universal covers. On this class, clique convergence is characterised using an explicit construction of the iterated clique graphs and a finite yet divergent parameter for the k-divergent case. Furthermore, it is shown that locally cyclic graphs with minimum degree δ ≥ 6 are k-convergent if and only if their universal covers are k-convergent. This way, the characterisation is completed.

This is joint work with Markus Baumeister and Martin Winter.