Clique polynomial: различия между версиями

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

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

:::::<math>w(C) = \prod_{\alpha \in C} w_{\alpha}.</math>

The '''clique polynomial''' of <math>\,G</math> is then:

:::::<math> K(G;\vec{w}) = \sum_{C} w(C),</math>

where the sum is taken over all the covers <math>\,C</math> of <math>\,G</math> and <math>\,\vec{w}</math> is the vector of indeterminates <math>\,w_{\alpha}</math>. If, for all <math>\,\alpha</math>, we set <math>\,w_{\alpha} = w</math>, then the resulting polynomial in the single

variable <math>\,w</math> is called a '''simple clique polynomial''' of  <math>\,G</math>.

Denote by <math>\,S(n,k)</math> the Stirling numbers of the second kind. Then

:::::<math>K(K_{n};w) = \sum_{k=0}^{n} S_{n,k}w^{k}.</math>