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^*(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.