Clique graph

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

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

[math]\displaystyle{ \lim_{n \rightarrow \infty} |V(k^{n}(G)| = \infty. }[/math]

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

Литература

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