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]