主題
Search

邊覆蓋多項式

下載 Mathematica 筆記本下載 Wolfram 筆記本

設 c_k 為圖 G 大小為 k 的 邊覆蓋 的數量。那麼邊覆蓋多項式 E_G(x) 定義為

E_G(x)=sum_(k=0)^mc_kx^k,
(1)

其中 m 是 G 的 邊數 (Akban and Oboudi 2013)。

迴圈圖和完全二部圖由它們的邊覆蓋多項式確定 (Akban and Oboudi 2013)。

邊覆蓋多項式在圖的元件上是乘法的，因此對於具有連通元件 G_1, G_2, ... 的圖 G，G 本身的邊覆蓋多項式由下式給出

E_G=E_(G_1)E_(G_2)....
(2)

邊覆蓋多項式滿足

E_G(-1)=(-1)^nI_G(-1),
(3)

其中 n=|G| 是圖 G 的 頂點數，I_G(x) 是它的 獨立多項式 (Akban and Oboudi 2013)。

下表總結了一些常見圖類的邊覆蓋多項式的和 (Akban and Oboudi 2013)。

圖E(x)
完全二部圖 K_(m,n)sum_(k=0)^(m)(-1)^k(m; k)[(x+1)^(m-k)-1]^n
完全圖 K_nsum_(k=0)^(n)(-1)^(n-k)(n; k)(x+1)^((k; 2))
迴圈圖 C_nx^n+sum_(k=1)^(n-1)n/(n-k)(k-1; n-k-1)x^k
路徑圖 P_nsum_(k=1)^(n-1)(k-1; n-k-1)x^k

下表總結了一些常見圖類的邊覆蓋多項式的閉合形式。

圖E(x)
書圖 S_(n+1) square P_2x^n-2[x(1+x)]^n+(1+x)[x(1+x(3+x))]^n
迴圈圖 C_n((x-sqrt(x(4+x)))^n+(x+sqrt(x(4+x)))^n)/(2^n)
輪狀圖-[x(1+x)]^n+[x(1+x)^2]^n
路徑圖 P_nsqrt(x/(x+4))((x+sqrt(x(4+x)))^(n-1)-(x-sqrt(x(4+x)))^(n-1))/(2^(n-1))
星圖 S_nx^(n-1)
日射圖 C_n circledot K_1[x(1+x)]^n

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

圖階數遞推關係
迴圈圖 C_n2p_n(x)=xp_(n-2)(x)+xp_(n-1)(x)
書圖 S_(n+1) square P_23p_n(x)=(x+1)(x^2+3x+1)x^3p_(n-3)(x)-(x^3+5x^2+8x+3)x^2p_(n-2)(x)+(x+1)(x+3)xp_(n-1)(x)
齒輪圖4p_n(x)=-(x+1)x^4p_(n-4)(x)+2(x+1)(x+2)x^3p_(n-3)(x)-(x+2)(x^2+3x+3)x^2p_(n-2)(x)+(x+2)^2xp_(n-1)(x)
輪狀圖2p_n(x)=x(x+1)(x+2)p_(n-1)(x)-x^2(x+1)^3p_(n-2)(x)
梯形圖 P_2 square P_n3p_n(x)=-(x+1)x^3p_(n-3)(x)+(x+2)x^3p_(n-2)(x)+(x+1)(x+2)xp_(n-1)(x)
莫比烏斯梯 M_n4p_n(x)=-(x+1)x^4p_(n-4)(x)+(x+2)(2x+1)x^2p_(n-2)(x)+(x^2+3x+1)xp_(n-1)(x)+(x^2+x-1)x^3p_(n-3)(x)
路徑圖 P_n2p_n(x)=xp_(n-2)(x)+xp_(n-1)(x)
稜柱圖 Y_n4p_n(x)=-(x+1)x^4p_(n-4)(x)+(x+2)(2x+1)x^2p_(n-2)(x)+(x^2+3x+1)xp_(n-1)(x)+(x^2+x-1)x^3p_(n-3)(x)
星圖 S_n1p_n(x)=xp_(n-1)(x)
日射圖 C_n circledot K_11p_n(x)=x(x+1)p_(n-1)(x)
網狀圖2p_n(x)=x^3(x+1)^3p_(n-2)(x)+x^2(x+2)(x+1)p_(n-1)(x)
輪圖 W_n4p_n(x)=-(x+1)x^2p_(n-4)(x)-(2x+3)x^2p_(n-3)(x)-(x-1)(x+2)xp_(n-2)(x)+(x+3)xp_(n-1)(x)

參見

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

使用 探索

參考文獻

Akban, S. 和 Oboudi, M. R. "關於圖的邊覆蓋多項式。" Europ. J. Combin. 34, 297-321, 2013.

引用為

Weisstein, Eric W. "邊覆蓋多項式。" 來自 Web 資源。 https://mathworld.tw/EdgeCoverPolynomial.html

主題分類