主題
Search

獨立多項式

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

設 s_k 為圖 G 中基數為 k 的獨立頂點集的數量。多項式

I(x)=sum_(k=0)^(alpha(G))s_kx^k,
(1)

其中 alpha(G) 是獨立數，被稱為圖 G 的獨立多項式 (Gutman and Harary 1983, Levit and Mandrescu 2005)。它也被稱為其他名稱，包括獨立集多項式 (Hoede and Li 1994) 或穩定集多項式 (Chudnovsky and Seymour 2004)。

獨立多項式與匹配多項式密切相關。 特別是，由於線圖 L(G) 中的獨立邊集對應於原始圖 G 中的獨立頂點集，因此圖 G 的匹配生成多項式等於圖 G 的線圖的獨立多項式 (Levit and Mandrescu 2005)

mu_G(x)=I_(L(G))(x).
(2)

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

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

其中 G^_ 表示圖的補圖 (Hoede and Li 1994)，並且透過下式與頂點覆蓋多項式相關

I_G(x)=x^nPsi_g(x^(-1)),
(4)

其中 n=|G| 是圖 G 的頂點數 (Akban and Oboudi 2013)。

不連通圖的獨立多項式等於其連通分量的獨立多項式的乘積。

可以使用 Wolfram 語言獲取許多命名圖的以變數 x 表示的預計算獨立多項式，方法是使用GraphData[graph,"IndependencePolynomial"][x].

下表總結了一些常見圖類的獨立多項式的閉合形式。這裡， s=sqrt(x^2+6x+1), t=sqrt(1+4x), 和 u=sqrt((x+1)(5x+1))。

圖I(x)
Andrásfai 圖 A_n1+(3n-1)x(x+1)^(n-1)
啞鈴圖[1+(n-1)x][1+(n+1)x]
書圖 S_(n+1) square P_22x(1+x)^n+(1+2x)^n
蜈蚣圖((-1+u-3x)(1-u+x)^n+(1+u+x)^n(1+u_3x))/(2^(n+1)u)
雞尾酒會圖 K_(n×2)1+nx(x+2)
完全二分圖 K_(n,n)2(x+1)^n-1
完全圖 K_n1+nx
完全三分圖 K_(n,n,n)3(x+1)^n-2
交叉稜柱圖2^(-n)[(1+2x(2+x)-sqrt((1+2x)(1+6x)))^n+(1+2x(2+x)+sqrt((1+2x)(1+6x)))^n]
冠圖2(x+1)^n+nx^2-1
圈圖 C_n2(-x)^(n/2)T_n(1/(2sqrt(-x)))
齒輪圖x(x+1)^n+((1-t+2x)^n+(1+t+2x)^n)/(2^n)
舵圖2^(-n)[2^nx(+x+1)^n+(x-u+1)^n+(x+u+1)^n]
梯形圖2^(-(n+1))[(s-3x-1)(x-s+1)^n+(s+3x+1)(x+s+1)^n]
梯子橫檔圖 nP_2(2x+1)^n
莫比烏斯梯子 M_n2^(-n)[-2^n(-x)^n+(x-s+1)^n+(x+s+1)^n]
平底鍋圖((1-t)^n(-x+t(2+x))+(1+t)^n(x+t(2+x)))/(2^(n+1)t)
路徑圖 P_nx^((n+1)/2)F_(n+2)(x^(-1/2))
稜柱圖2^(-n)[2^n(-x)^n+(1+x-s)^n+(1+x+s)^n]
星圖 S_nx+(1+x)^(n-1)
太陽圖(x+1)^(n-2)[1+x(x+n+2)]
太陽花圖 C_n circledot K_12^(-n)[(u+x+1)^n+(-u+x+1)^n]
三角形圖2^(-n/2)(-isqrt(x))^nH_n(i/(sqrt(2x)))
=2^(n/2)(-1/x)^(-n/2)U(1/2n,1/2,1/(2x))
輪圖 W_n(-(1-t)^n-(1-t)^nt+(t-1)(1+t)^n+2^(n-1)x^2)/(2^(n+1)x)

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

圖階數遞推關係
Andrásfai 圖3p_n(x)=(2x+3)p_(n-1)(x)-(x+1)(x+3)p_(n-2)(x)+(x+1)^2p_(n-3)(x)
反稜柱圖3p_n(x)=x^2p_n-3(x)+2xp_n-2(x)+p_n-1(x)
啞鈴圖3p_n(x)=3p_(n-1)(x)-3p_(n-2)(x)+p_(n-3)(x)
書圖 S_(n+1) square P_22p_n(x)=(3x+2)p_(n-1)(x)-(x+1)(2x+1)p_(n-2)(x)
蜈蚣圖2p_n(x)=(x+1)p_(n-1)(x)+x(x+1)p_(n-2)(x)
雞尾酒會圖 K_(n×2)2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
完全二分圖 K_(n,n)2p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
交叉稜柱圖2p_n(x)=(2x^2+4x+1)p_(n-1)(x)-x^2(x^2+4x+2)p_(n-2)(x)
冠圖3p_n(x)=(x+3)p_(n-1)(x)-(2x+3)p_(n-2)(x)+(x+1)p_(n-3)(x)
圈圖 C_n2p_n(x)=p_(n-1)(x)+xp_(n-2)(x)
齒輪圖3p_n(x)=(3x+2)p_(n-1)(x)-(3x^2+3x+1)p_(n-2)(x)+(x+1)x^2p_(n-3)(x)
舵圖3p_n(x)=2(x+1)p_(n-1)(x)-(x+1)p_(n-2)(x)-x(x+1)^2p_(n-3)(x)
梯形圖2p_n(x)=(x+1)p_(n-1)(x)+xp_(n-2)(x)
梯子橫檔圖1p_n(x)=(2x+1)p_(n-1)(x)
莫比烏斯梯子 M_n3p_n(x)=p_(n-1)(x)+x(x+2)p_(n-2)(x)+x^2p_(n-3)(x)
平底鍋圖2p_n(x)=p_(n-1)(x)+xp_(n-2)(x)
路徑圖 P_n2p_n(x)=p_(n-1)(x)+xp_(n-2)(x)
稜柱圖 Y_n3p_n(x)=p_(n-1)(x)+x(x+2)p_(n-2)(x)+x^2p_(n-3)(x)
星圖 S_n2p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
太陽圖2p_n(x)=2(x+1)p_(n-1)(x)-(x+1)^2p_(n-2)(x)
太陽花圖 C_n circledot K_12p_n(x)=(x+1)p_(n-1)(x)+x(x+1)p_(n-2)(x)
網圖3p_n(x)=(x+1)p_(n-1)(x)+2x(x+1)^2p_(n-2)(x)+x^2(x+1)^2p_(n-3)(x)
輪圖 W_n3p_n(x)=2p_(n-1)(x)+(x-1)p_(n-2)(x)-xp_(n-3)(x)

非同構圖不一定具有不同的獨立多項式。下表總結了一些同獨立多項式圖。

n獨立多項式圖
4(1+x)(1+3x)(4,6), 路徑圖 P_4
41+4x+2x^2爪圖, 方形圖
5(1+x)^2(1+3x)(5,8), (5,9)
5(1+x)(1+4x)蝴蝶圖, 房子圖, 風箏圖, (5,24)
5(1+x)(1+4x+x^2)橫幅圖, 公牛圖, (5,15)
5(1+x)(1+4x+2x^2)叉圖, (5,10), (5,14)
51+5x+2x^2房子 X 圖, 輪圖 W_5
51+5x+3x^2寶石圖, (5,31), (4,1)-棒棒糖圖
51+5x+5x^2圈圖 C_5, (3,2)-蝌蚪圖
51+5x+4x^2+x^3飛鏢圖, 完全二分圖 K_(2,3)

樹的獨立多項式是單峰的，無爪圖的獨立多項式是對數凹的。

另請參閱

團多項式, 獨立數, 獨立集, 較低獨立數, 匹配多項式

使用 探索

參考文獻

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Discrete Mathematics 163, 47-66, 1997.Chudnovsky, M. and Seymour, P. "The Roots of the Stable Set Polynomial of a Claw-Free Graph." 2004. http://www.math.princeton.edu/÷mchudnov/publications.html.Gutman, I. and Harary, F. "Generalizations of the Matching Polynomial." Utilitas Mathematica 24, 97-106, 1983.Hoede, C. and Li, X. "Clique Polynomials and Independent Set Polynomials of Graphs." Discrete Mathematics 125, 219-228, 1994.Levit, V. E. and Mandrescu, E. "The Independence Polynomial of a Graph--A Survey." In 第一屆代數資訊學國際會議論文集. 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/IndependencePolynomial.html

主題分類