主题
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)

另请参阅

边覆盖多项式, 顶点覆盖, 顶点覆盖数

使用 Wolfram|Alpha 探索

参考文献

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. “顶点覆盖多项式。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/VertexCoverPolynomial.html

主题分类