The Clique Behavior of Circulants With Three Small Jumps

Abstract

The clique graph $K(G)$ of a graph $G$ is the intersection graph of all its (maximal) cliques, and $G$ is said to be clique divergent if the order of its $n$-th iterated clique graph $K^n(G)$ tends to infinity with $n$. In general, deciding whether a graph is clique divergent is not known to be computable. We characterize the dynamical behavior under the clique operator of circulant graphs of the form $C_n(a,b,c)$ with $0<a<b<c<\frac{n}{3}$. Such a circulant is clique divergent if and only if it is not clique-Helly. Owing to the Dragan-Szwarcfiter Criterion to decide clique-Hellyness, our result implies that the clique divergence of these circulants can be decided in polynomial time. Our main difficulty was the case $C_n(1,2,4)$, which is clique divergent but no previously known technique could be used to prove it.