Clique polynomial

Clique polynomial — кликовый полином.

Let [math]\displaystyle{ \,G }[/math] be a finite, simple graph and let [math]\displaystyle{ \,F }[/math] be a family of cliques. By a clique cover of [math]\displaystyle{ \,G }[/math] we mean a spanning subgraph of [math]\displaystyle{ \,G }[/math], each component of which is a member of [math]\displaystyle{ \,F }[/math]. With each element [math]\displaystyle{ \,\alpha }[/math] of [math]\displaystyle{ \,F }[/math] we associate an indeterminate (or weight) [math]\displaystyle{ \,w_{\alpha} }[/math] and with each cover [math]\displaystyle{ \,C }[/math] of [math]\displaystyle{ \,G }[/math] we associate the weight

[math]\displaystyle{ w(C) = \prod_{\alpha \in C} w_{\alpha}. }[/math]

The clique polynomial of [math]\displaystyle{ \,G }[/math] is then:

[math]\displaystyle{ K(G;\vec{w}) = \sum_{C} w(C), }[/math]

where the sum is taken over all the covers [math]\displaystyle{ \,C }[/math] of [math]\displaystyle{ \,G }[/math] and [math]\displaystyle{ \,\vec{w} }[/math] is the vector of indeterminates [math]\displaystyle{ \,w_{\alpha} }[/math]. If, for all [math]\displaystyle{ \,\alpha }[/math], we set [math]\displaystyle{ \,w_{\alpha} = w }[/math], then the resulting polynomial in the single variable [math]\displaystyle{ \,w }[/math] is called a simple clique polynomial of [math]\displaystyle{ \,G }[/math].

Denote by [math]\displaystyle{ \,S(n,k) }[/math] the Stirling numbers of the second kind. Then

[math]\displaystyle{ K(K_{n};w) = \sum_{k=0}^{n} S_{n,k}w^{k}. }[/math]

Литература

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