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

树的独立多项式是单峰的，无爪图的独立多项式是对数凹的。

另请参阅

团多项式, 独立数, 独立集, 较低独立数, 匹配多项式

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上被引用

独立多项式

请这样引用

Weisstein, Eric W. "独立多项式。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/IndependencePolynomial.html

主题分类