The $K$-Behaviour of $p$-Trees

Abstract

Let $G=(V,E)$ be a graph with $n$ vertices. The clique graph of $G$ is the intersection graph $K(G)$ of the set of all (maximal) cliques of $G$ and $K$ is called the clique operator. The iterated clique graphs $K^{\ast }(G)$ are recursively defined by $K^0(G)=G$ and $K^i(G)=K(K^{i-1}(G))$, $i>0$. A graph is $K$-divergent if the sequence $|V(K^i(G))|$ of all vertex numbers of its iterated clique graphs is unbounded, otherwise it is $K$-convergent. The long-run behaviour of $G$, when we repeatedly apply the clique operator, is called the $K$-behaviour of $G$.

In this paper, we characterize the $K$-behaviour of the class of graphs called $p$-trees, that has been extensively studied by Babel. Among many other properties, a $p$-tree contains exactly $n–3$ induced $4$-cycles. In this way, we extend some previous results about the $K$-behaviour of cographs, i.e., graphs with no induced $P_4$s. This characterization leads to a polynomial-time algorithm for deciding the $K$-convergence or $K$-divergence of any graph in the class.