主題
Search

團多項式

圖 G 的團多項式 C_G(x) 定義為多項式

C_G(x)=1+sum_(k=1)^(omega(G))c_kx^k,
(1)

其中 omega(G) 是 G 的團數，對於 k>0，x_k 的係數是圖中 團 c_k 的數量，常數項為 1 (Hoede 和 Li 1994, Hajiabolhassan 和 Mehrabadi 1998)。Hajiabolhassan 和 Mehrabadi (1998) 證明了 C_G(x) 總是有一個實根。

係數 c_1 是頂點計數，c_2 是邊計數，而 c_3 是圖中三角形計數。

C_G(x) 與獨立多項式透過下式相關

C_G(x)=I_(G^_)(x),
(2)

其中 G^_ 表示圖的補圖 (Hoede 和 Li 1994)。

這個多項式類似於依賴多項式，定義為

D_G(x)=1+sum_(k=1)^(omega(G))(-1)^kc_kx^k
(3)

(Fisher 和 Solow 1990)，兩者透過下式相關

C_G(x)=D_G(-x).
(4)

下表總結了一些常見圖類的團多項式。

圖C(x)
Andrásfai 圖 A_n1+1/2(3n-1)x(nx+2)
反稜柱圖{(2x+1)(4x^2+6x+1) for n=3; nx^2+nx+1 otherwise
啞鈴圖-1+x^2+2(1+x)^n
書圖 S_(n+1) square P_2(3n+1)x^2+x^2+2(n+1)x+1
雞尾酒會圖 K_(n×2)(1+2x)^n
完全二部圖 K_(m,n)(1+mx)(1+nx)
完全圖 K_n(1+x)^n
完全三部圖 K_(l,m,n)(1+lx)(1+mx)(1+nx)
交叉稜柱圖3nx^2+2nx+1
冠圖n(n-1)x^2+2nx+1
圈圖 C_n{(1+x)^3forn=3 ; 1+nx+nx^2 otherwise
空圖 K^__nnx+1
摺疊立方體圖{(x+1)^(2(n-1)) for n=2,3; 1+2^(n-2)x(nx+2) otherwise
齒輪圖3nx^2+x(2n+1)x+1
網格圖 P_m×P_n1+mnx+(2mn-m-n)x^2
網格圖 P_l×P_m×P_n1+lmnx+(3lmn-lm-ln-mn)x^2
舵圖{(1+x)(1+6x+3x^2+x^3) for n=3; (1+x)(1+2nx+nx^2) otherwise
超立方體圖 Q_n2^(n-1)x(2+nx)+1
m×n-國王圖{(1+x)^2(1+(n-1)x(2+x)) for m=2; (1+x)(1+(mn-1)x+3(m-1)(n-1)x^2+(m-1)(n-1)x^3) otherwise
m×n-騎士圖1+mnx+2(2mn-3m-3n+4)x^2
梯子圖 P_2 square P_n1-2x^2+nx(2+3x)
梯子橫檔圖 nP_21+nx(2+x)
莫比烏斯梯子 M_n1+nx(2+3x)
路徑圖 P_n(1+x)(1+(-1+n)x)
稜柱圖 Y_n{(2x+1)(x^2+4x+1) for n=3; 1+nx(2+3x) otherwise
星圖 S_n(1+x)(1+(-1+n)x)
太陽圖nx(1+x)^2+(1+x)^n
太陽花圖 C_n circledot K_11+2nx(1+x)
轉置圖1+n!x+1/4n!n(n-1)x^2
三角形網格圖1/2(1+x)(2+nx(3+n+2nx))
網圖 對於 n>31+3nx+4nx^2
輪圖 W_n{(1+x)^4 for n=4; (1+x)(1+(-1+n)x(1+x)) otherwise

下表總結了一些簡單圖類的團多項式的遞推關係。

圖階數遞推關係
Andrásfai 圖 A_n4p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
啞鈴圖2p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
書圖 S_(n+1) square P_22p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
雞尾酒會圖 K_(n×2)1p_n(x)=(2x+1)p_(n-1)(x)
完全二部圖 K_(n,n)3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
完全圖 K_n1p_n(x)=(x+1)p_(n-1)(x)
(2n)-交叉稜柱圖2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
冠圖3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
圈圖 C_n 對於 n>=42p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
空圖 K^__n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
摺疊立方體圖3p_n(x)=4p_(n-3)(x)-8p_(n-2)(x)+5p_(n-1)(x)
齒輪圖2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
網格圖 P_n×P_n3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
網格圖 P_n×P_n×P_n4p_n(x)=-p_(n-4)(x)+4p_(n-3)(x)-6p_(n-2)(x)+4p_(n-1)(x)
超立方體圖 Q_n3p_n(x)=4p_(n-3)(x)-8p_(n-2)(x)+5p_(n-1)(x)
n×n-國王圖3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
n×n-騎士圖3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
梯子圖 P_2 square P_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
梯子橫檔圖 nP_22p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
莫比烏斯梯子 M_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
路徑圖 P_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
稜柱圖 Y_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
星圖 S_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
太陽圖3p_n(x)=(x+1)p_(n-3)(x)-(2x+3)p_(n-2)(x)+(x+3)p_(n-1)(x)
太陽花圖 C_n circledot K_12p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
三角形網格圖3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
輪圖 W_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)

另請參閱

團, 團數

使用 探索

參考文獻

Fisher, D. C. and Solow, A. E. "Dependence Polynomials." Disc. Math. 82, 251-258, 1990.Goldwurm, M. and Santini, M. "Clique Polynomials Have a Unique Root of Smallest Modulus." Informat. Proc. Lett. 75, 127-132, 2000.Hajiabolhassan, H. and Mehrabadi, M. L. "On Clique Polynomials." Australas. J. Combin. 18, 313-316, 1998.Hoede, C. and Li, X. "Clique Polynomials and Independent Set Polynomials of Graphs." Discr. Math. 125, 219-228, 1994.Levit, V. E. and Mandrescu, E. "The Independence Polynomial of a Graph--A Survey." In Proceedings of the 1st International Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005 (Ed. S. Bozapalidis, A. Kalampakas, and G. Rahonis). Thessaloniki, Greece: Aristotle Univ., pp. 233-254, 2005.

請引用為

Weisstein, Eric W. "團多項式。" 來自 Web 資源。 https://mathworld.tw/CliquePolynomial.html

主題分類