Clique dynamics of locally cyclic graphs with $\delta \ge 6$

Abstract

We prove that the clique graph operator $k$ is divergent on a locally cyclic graph $G$ (i.e. $N_G(v)$ is a circle) with minimum degree $\delta (G)=6$ if and only if $G$ is $6$-regular. The clique graph $kG$ of a graph $G$ has the maximal complete subgraphs of $G$ as vertices, and the edges are given by non-empty intersections. If all iterated clique graphs of $G$ are pairwise non-isomorphic, the graph $G$ is $k$-divergent; otherwise, it is $k$-convergent. To prove our claim, we explicitly construct the iterated clique graphs of those infinite locally cyclic graphs with $\delta \ge 6$ which induce simply connected simplicial surfaces. These graphs are $k$-convergent if the size of triangular-shaped subgraphs of a specific type is bounded from above. We apply this criterion by using the universal cover of the triangular complex of an arbitrary finite locally cyclic graph with $\delta =6$, which shows our divergence characterisation.

36 pages, 16 figures