Clique graph

Clique graph — граф клик.

The clique graph $\,k(G)$ is the intersection graph of the set of all cliques of $\,G$. The iterated clique graphs are defined recursively by $\,k^{0}(G) = G$ and $\,k^{n+1}(G) = k(k^{n}(G))$. A graph $\,G$ is said to be clique divergent (or $\,k$-divergent) if

$\lim_{n \rightarrow \infty} |V(k^{n}(G)| = \infty.$

A graph $\,G$ is said to be $\,k$-convergent if $k^{n}(G) \cong k^{m}(G)$ for some $n \neq m$; when $\,m = 0$, we say that $\,G$ is $\,k$-invariant. $\,G$ is $\,k$-null if $\,k^{n}(G)$ is trivial (one vertex) for some $\,n$ (clearly, a special case of a $\,k$-covergent graph). It is easy to see that every graph is either $\,k$-convergent or $\,k$-divergent.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.