# 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$.

Denote by $\,S(n,k)$ the Stirling numbers of the second kind. Then $K(K_{n};w) = \sum_{k=0}^{n} S_{n,k}w^{k}.$

## Литература

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