Clique graph

Материал из WikiGrapp
Перейти к:навигация, поиск

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.