Clique polynomial

Материал из WikiGrapp
Перейти к:навигация, поиск

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.