主題
Search

頂點覆蓋多項式

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

令 c_k 為圖 G 大小為 k 的頂點覆蓋的數量。則頂點覆蓋多項式 Psi_G(x) 定義為

Psi_G(x)=sum_(k=0)^(|G|)c_kx^k,
(1)

其中 |G| 是 G 的頂點計數 (Dong 等人，2002年)。

它與獨立多項式 I_G(x) 相關，關係如下

Psi_G(x)=x^nI_G(x^(-1))
(2)

(Akban 和 Oboudi，2013年)。

許多命名圖的頂點覆蓋多項式的預計算形式，以變數 x 表示，可以在 Wolfram Language 中使用以下方法獲得：GraphData[graph,"VertexCoverPolynomial"][x].

下表總結了一些常見圖類的頂點覆蓋多項式的閉合形式 (參見 Dong 等人，2002年)。

圖Psi(x)
Andrásfai 圖 A_nx^(2n-1)[x^n+(3n-1)(x+1)^(n-1)]
啞鈴圖x^(2n-2)(x+n+1)(x+n-1)
書圖 S_(n+1)P_2x{2[x(x+1)]^n+x[x(x+2)]^n}
雞尾酒會圖x^(2n-2)(n+2nx+x^2)
完全二分圖 K_(m,n)x^m(1+x)^n+x^n(1+x)^m-x^(m+n)
完全二分圖 K_(n,n)2x^n(x+1)^n-x^(2n)
完全圖 K_nx^n+nx^(n-1)
完全三部圖 K_(n,n,n)3[x^2(x+1)]^n-2x^(3n)
冠圖x^(2n-2)(n-x^2)+2[x+(x+1)]^n
圈圖 C_nsum_(k=1)^(n)n/k(k; n-k)x^k
空圖 K^__n(1+x)^n
齒輪圖[x(x+1)]^n+(x{[x(2+x-sqrt(x(4+x)))]^n+[x(2+x+sqrt(x(4+x)))]^n})/(2^n)
舵圖[x(1+x)]^n+2^(-n)x{[x(1+x-sqrt((1+x)(5+x)))]^n+[x(1+x+sqrt((1+x)(5+x)))]^n}
梯子橫檔圖 nP_2[x(x+2)]^n
莫比烏斯梯子 M_n(-2^n(-x)^n+[x(1+x-sqrt(1+x(6+x)))]^n+[x(1+x+sqrt(1+x(6+x)))]^n)/(2^n)
路徑圖 P_nsum_(k=0)^(n)(k+1; n-k)x^k
稜柱圖2^(-n)[(-2)^nx^n+[x(1+x-sqrt(1+x(6+x)))]^n+[x(1+x-+sqrt1+x(6+x))]^n]
星圖 S_nx+(1+x)^(n-1)
太陽圖(1+x)^(n-2)[1+x(2+n+x)]
日光圖 C_n circledot K_12^(-n)[(1+x-sqrt((1+x)(1+5x)))^n+(1+x+sqrt((1+x)(1+5x)))^n]
輪圖 W_nx^(n-1)+sum_(k=2)^(n)(n-1)/(k-1)(k-1; n-k)x^k

圈圖 C_n 的等價形式包括

Psi_(C_n)=sum_(k=1)^(n)n/k(k; n-k)x^k
(3)
=([x-sqrt(x(4+x))]^n+[x+sqrt(x(4+x))]^n)/(2^n).
(4)
圖階數遞推關係
Andrásfai 圖3p_n(x)=(x+1)^2x^2p_(n-3)(x)-(x+1)(3x+1)x^4p_(n-2)(x)+(3x+2)x^2p_(n-1)(x)
反稜柱圖 Y_n3p_n(x)=x^4p_(n-3)(x)+2x^3p_(n-2)(x)+x^2p_(n-1)(x)
啞鈴圖3p_n(x)=x^6p_(n-3)(x)-3x^4p_(n-2)(x)+3x^2p_(n-1)(x)
書圖 S_(n+1)P_22p_n(x)=-x^2(x+1)(x+2)p_(n-2)(x)+x(2n+3)p_(n-1)(x)
蜈蚣圖2p_n(x)=(x+1)x^2p_(n-2)(x)+(x+1)xp_(n-1)(x)
雞尾酒會圖2p_n(x)=-x^4p_(n-2)(x)+2x^2p_(n-1)(x)
完全二分圖 K_(n,n)2p_n(x)=-x^3(x+1)2p_(n-2)(x)+x(2x+1)p_(n-1)(x)
完全圖 K_n2p_n(x)=-x^2p_(n-2)(x)+2xp_(n-1)(x)
完全三部圖 K_(n,n,n)2p_n(x)=-x^5(x+1)p_(n-2)(x)+x^2(2x+1)p_(n-1)(x)
交叉稜柱圖2p_(2n)(x)=-x^4(2x^2+4x+1)p_(2n-2)(x)+x^2(x^2+4x+2)p_(2n-1)(x)
冠圖3p_n(x)=x^5(x+1)p_(n-3)(x)-(3x+2)x^3p_(n-2)(x)+(3x+1)xp_(n-1)(x)
圈圖 C_n2p_n(x)=xp_(n-2)(x)+xp_(n-1)(x)
空圖 K^__n1p_n(x)=(x+1)p_(n-1)(x)
齒輪圖3p_n(x)=(x+1)x^3p_(n-3)(x)-(x^2+3x+3)x^2p_(n-2)(x)+(2x+3)xp_(n-1)(x)
舵圖3p_n(x)=-(x+1)^2x^3p_(n-3)(x)-(x+1)x^3p_(n-2)(x)+2(x+1)xp_(n-1)(x)
梯子圖2p_n(x)=x^3p_(n-2)(x)+(x+1)xp_(n-1)(x)
梯子橫檔圖1p_n(x)=x(x+2)p_(n-1)(x)
莫比烏斯梯子 M_n3p_n(x)=x^4p_(n-3)(x)+(2x+1)x^2p_(n-2)(x)+x^2p_(n-1)(x)
盤圖2p_n(x)=xp_(n-2)(x)+xp_(n-1)(x)
路徑圖 P_n2p_n(x)=xp_(n-2)(x)+xp_(n-1)(x)
稜柱圖 Y_n3p_n(x)=x^4p_(n-3)(x)+(2x+1)x^2p_(n-2)(x)+x^2p_(n-1)(x)
星圖 S_n2p_n(x)=(-x-1)p_(n-2)(x)+(x+2)p_(n-1)(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(x+1)p_(n-2)(x)+(x+1)p_(n-1)(x)
網圖3p_n(x)=(x+1)^2x^5p_(n-3)(x)+2(x+1)^2x^3p_(n-2)(x)+(x+1)x^2p_(n-1)(x)
輪圖 W_n3p_n(x)=-xp_(n-3)(x)+(x-1)p_(n-2)(x)+2p_(n-1)(x)

另請參閱

邊覆蓋多項式, 頂點覆蓋, 頂點覆蓋數

使用 探索

參考文獻

Akban, S. and Oboudi, M. R. “關於圖的邊覆蓋多項式。” Europ. J. Combin. 34, 297-321, 2013.Csikvári, P. and Oboudi, M. R. “關於圖的邊覆蓋多項式的根。” Europ. J. Combin. 32, 1407-1416, 2011.Dong, F. M.; Hendy, M. D.; Teo, K. L.; and Little, C. H. C. “圖的頂點覆蓋多項式。” Discr. Math. 250, 71-78, 2002.

引用為

Weisstein, Eric W. “頂點覆蓋多項式。” 來自 Web 資源。 https://mathworld.tw/VertexCoverPolynomial.html

主題分類