Clique polynomial

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

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

w(C) = \prod_{\alpha \in C} w_{\alpha}.

The clique polynomial of $\,G$ is then:

K(G;\vec{w}) = \sum_{C} w(C),

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