主题
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.net.cn/EdgeCoverPolynomial.html

主题分类