主题
Search

团多项式

图 G 的团多项式 C_G(x) 定义为多项式

C_G(x)=1+sum_(k=1)^(omega(G))c_kx^k,
(1)

其中 omega(G) 是 G 的团数，对于 k>0，x_k 的系数是图中 团 c_k 的数量，常数项为 1 (Hoede 和 Li 1994, Hajiabolhassan 和 Mehrabadi 1998)。Hajiabolhassan 和 Mehrabadi (1998) 证明了 C_G(x) 总是有一个实根。

系数 c_1 是顶点计数，c_2 是边计数，而 c_3 是图中三角形计数。

C_G(x) 与独立多项式通过下式相关

C_G(x)=I_(G^_)(x),
(2)

其中 G^_ 表示图的补图 (Hoede 和 Li 1994)。

这个多项式类似于依赖多项式，定义为

D_G(x)=1+sum_(k=1)^(omega(G))(-1)^kc_kx^k
(3)

(Fisher 和 Solow 1990)，两者通过下式相关

C_G(x)=D_G(-x).
(4)

下表总结了一些常见图类的团多项式。

图C(x)
Andrásfai 图 A_n1+1/2(3n-1)x(nx+2)
反棱柱图{(2x+1)(4x^2+6x+1) for n=3; nx^2+nx+1 otherwise
哑铃图-1+x^2+2(1+x)^n
书图 S_(n+1) square P_2(3n+1)x^2+x^2+2(n+1)x+1
鸡尾酒会图 K_(n×2)(1+2x)^n
完全二部图 K_(m,n)(1+mx)(1+nx)
完全图 K_n(1+x)^n
完全三部图 K_(l,m,n)(1+lx)(1+mx)(1+nx)
交叉棱柱图3nx^2+2nx+1
冠图n(n-1)x^2+2nx+1
圈图 C_n{(1+x)^3forn=3 ; 1+nx+nx^2 otherwise
空图 K^__nnx+1
折叠立方体图{(x+1)^(2(n-1)) for n=2,3; 1+2^(n-2)x(nx+2) otherwise
齿轮图3nx^2+x(2n+1)x+1
网格图 P_m×P_n1+mnx+(2mn-m-n)x^2
网格图 P_l×P_m×P_n1+lmnx+(3lmn-lm-ln-mn)x^2
舵图{(1+x)(1+6x+3x^2+x^3) for n=3; (1+x)(1+2nx+nx^2) otherwise
超立方体图 Q_n2^(n-1)x(2+nx)+1
m×n-国王图{(1+x)^2(1+(n-1)x(2+x)) for m=2; (1+x)(1+(mn-1)x+3(m-1)(n-1)x^2+(m-1)(n-1)x^3) otherwise
m×n-骑士图1+mnx+2(2mn-3m-3n+4)x^2
梯子图 P_2 square P_n1-2x^2+nx(2+3x)
梯子横档图 nP_21+nx(2+x)
莫比乌斯梯子 M_n1+nx(2+3x)
路径图 P_n(1+x)(1+(-1+n)x)
棱柱图 Y_n{(2x+1)(x^2+4x+1) for n=3; 1+nx(2+3x) otherwise
星图 S_n(1+x)(1+(-1+n)x)
太阳图nx(1+x)^2+(1+x)^n
太阳花图 C_n circledot K_11+2nx(1+x)
转置图1+n!x+1/4n!n(n-1)x^2
三角形网格图1/2(1+x)(2+nx(3+n+2nx))
网图 对于 n>31+3nx+4nx^2
轮图 W_n{(1+x)^4 for n=4; (1+x)(1+(-1+n)x(1+x)) otherwise

下表总结了一些简单图类的团多项式的递推关系。

图阶数递推关系
Andrásfai 图 A_n4p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
哑铃图2p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
书图 S_(n+1) square P_22p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
鸡尾酒会图 K_(n×2)1p_n(x)=(2x+1)p_(n-1)(x)
完全二部图 K_(n,n)3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
完全图 K_n1p_n(x)=(x+1)p_(n-1)(x)
(2n)-交叉棱柱图2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
冠图3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
圈图 C_n 对于 n>=42p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
空图 K^__n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
折叠立方体图3p_n(x)=4p_(n-3)(x)-8p_(n-2)(x)+5p_(n-1)(x)
齿轮图2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
网格图 P_n×P_n3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
网格图 P_n×P_n×P_n4p_n(x)=-p_(n-4)(x)+4p_(n-3)(x)-6p_(n-2)(x)+4p_(n-1)(x)
超立方体图 Q_n3p_n(x)=4p_(n-3)(x)-8p_(n-2)(x)+5p_(n-1)(x)
n×n-国王图3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
n×n-骑士图3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
梯子图 P_2 square P_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
梯子横档图 nP_22p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
莫比乌斯梯子 M_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
路径图 P_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
棱柱图 Y_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
星图 S_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
太阳图3p_n(x)=(x+1)p_(n-3)(x)-(2x+3)p_(n-2)(x)+(x+3)p_(n-1)(x)
太阳花图 C_n circledot K_12p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
三角形网格图3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
轮图 W_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)

另请参阅

团, 团数

使用 Wolfram|Alpha 探索

参考文献

Fisher, D. C. and Solow, A. E. "Dependence Polynomials." Disc. Math. 82, 251-258, 1990.Goldwurm, M. and Santini, M. "Clique Polynomials Have a Unique Root of Smallest Modulus." Informat. Proc. Lett. 75, 127-132, 2000.Hajiabolhassan, H. and Mehrabadi, M. L. "On Clique Polynomials." Australas. J. Combin. 18, 313-316, 1998.Hoede, C. and Li, X. "Clique Polynomials and Independent Set Polynomials of Graphs." Discr. Math. 125, 219-228, 1994.Levit, V. E. and Mandrescu, E. "The Independence Polynomial of a Graph--A Survey." In Proceedings of the 1st International Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005 (Ed. S. Bozapalidis, A. Kalampakas, and G. Rahonis). Thessaloniki, Greece: Aristotle Univ., pp. 233-254, 2005.

请引用为

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

主题分类