主题
Search

支配多项式

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

设 d_G(k) 为图 G 中大小为 k 的支配集的数量，则变量 x 中图 G 的支配多项式 D_G(x) 定义为

D_G(x)=sum_(k=gamma(G))^(|V(G)|)d_G(k)x^k,

其中 gamma(G) 是图 G 的（下）支配数 (Kotek 等人 2012, Alikhani 和 Peng 2014)。

D_G(x) 在连通分量上是可乘的 (Alikhani 和 Peng 2014)。

非同构图可能具有相同的支配多项式。如果图具有相等的支配多项式，则称这些图是支配等价的；如果一个图与任何其他非同构图都不共享支配多项式，则称该图是支配唯一的 (Akbari 等人 2010)。

支配多项式的根称为支配根 (Akbari 等人 2010)。

找到一般图的最小支配集，以及因此支配多项式，是 NP 完全问题，这可以通过从顶点覆盖问题的归约来证明 (Garey 和 Johnson 1983, Mertens 2024)。这意味着不存在多项式时间算法来计算支配多项式（甚至支配数）。已知最快的找到顶点计数 |G| 的一般图的最小支配集的算法的时间复杂度为 O(1.4969|G|) (van Rooij 和 Bodlaender 2011, Mertens 2024)。

许多命名图的预计算支配多项式，以变量 x 表示，并在 Wolfram 语言中表示为GraphData[图,"DominationPolynomial"][x].

下表总结了一些常见图类的支配多项式的闭合形式（参见 Alikhani 和 Peng 2014）。

图D(x)
哑铃图[-1+(1+x)^n]^2
书图 S_(n+1) square P_2-2x^n+x^2(1+x)^((2n))+[x(2+x)]^n(1+2x)
鸡尾酒会图 K_(n×2)(x+1)^(2n)-2nx-1
完全二部图 K_(m,n)[(x+1)^m-1][(1+x)^n-1]+x^m+x^n
完全图 K_n(x+1)^n-1
空图 K^__nx^n
舵图x^n[(x+1)(x+2)^n-1]
日珥图 C_n circledot K_1[x(x+2)]^n

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

图阶数递推关系
反棱柱图5p_n(x)=x^2p_(n-5)(x)+x^2p_(n-4)(x)+x^2p_(n-3)(x)+(x+2)xp_(n-2)(x)+(x+2)xp_(n-1)(x)
哑铃图3p_n(x)=-(x^2+3x+3)(x+1)p_(n-2)(x)+(x^2+3x+3)p_(n-1)(x)+(x+1)^3p_(n-3)(x)
书图 S_(n+1) square P_23p_n(x)=x^2(x+2)(x+1)^2p_(n-3)(x)+(2x^2+5x+1)p_(n-1)(x)-x(x^3+6x^2+9x+3)p_(n-2)(x)
鸡尾酒会图 K_(n×2)3p_n(x)=-(2x^2+4x+3)p_(n-2)(x)+(x^2+2x+3)p_(n-1)(x)+(x+1)^2p_(n-3)(x)
完全图 K_n2p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
圈图 C_n3p_n(x)=xp_(n-3)(x)+xp_(n-2)(x)+xp_(n-1)(x)
空图 K^__n1p_n(x)=xp_(n-1)(x)
齿轮图6p_n(x)=(x+1)x^4p_(n-6)(x)+(x+2)(2x-1)x^3p_(n-4)(x)+(2x^2+2x-1)x^3p_(n-5)(x)+(x^3+2x^2-3x-2)x^2p_(n-3)(x)-(x^3+6x^2+6x-1)xp_(n-2)(x)+(2x+5)xp_(n-1)(x)
舵图2p_n(x)=x(x+3)p_(n-1)(x)-x^2(x+2)p_(n-2)(x)
梯子图 P_2 square P_n5p_n(x)=-x^3p_(n-5)(x)-x^3p_(n-4)(x)+(x+1)x^2p_(n-3)(x)+(x+1)xp_(n-2)(x)+(x+2)xp_(n-1)(x)
路径图 P_n3p_n(x)=xp_(n-3)(x)+xp_(n-2)(x)+xp_(n-1)(x)
星图 S_n2p_n(x)=(2x+1)p_(n-1)(x)-x(x+1)p_(n-2)(x)
太阳图2p_n(x)=x(x+1)p_(n-2)(x)+x(x+2)p_(n-1)(x)
日珥图 C_n circledot K_11p_n(x)=x(x+2)p_(n-1)(x)
网图3p_n(x)=(x+2)^2x^4p_(n-3)(x)+(x+2)x^3p_(n-2)(x)+(x^2+3x+1)xp_(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)

另请参阅

点色数, 点色划分, 支配集, 支配数, 上支配数

使用 Wolfram|Alpha 探索

参考文献

Akbari, S.; Alikhani, S.; 和 Peng, Y.-H. "使用支配多项式表征图。" Eur. J. Combin. 31, 1714-1724, 2010.Alikhani, S. 和 Peng, Y.-H. "圈的支配集和支配多项式。" Global J. Pure Appl. Math. 4, No. 2, 2008.Alikhani, S. 和 Peng, Y.-H. "图的支配多项式导论。" Ars Combin. 114, 257-266, 2014.Garey, M. R. 和 Johnson, D. S. 计算机和难解性：NP-完全性理论指南。 New York: W. H. Freeman, pp. 155-157 和 288, 1983.Burger, A. P.; Cockayne, E. J.; 和 Mynhardt, C. M. "皇后图中的支配和冗余。" Disc. Math. 163, 47-66, 1997.Haynes, T. W.; Hedetniemi, S. T.; 和 Slater, P. J. 图的支配基础。 New York: Dekker, 1998.Hedetniemi, S. T. 和 Laskar, R. C. "图的支配集和支配参数的一些基本定义的参考书目。" Disc. Math. 86, 257-277, 1990.Kotek, T.; Preen, J.; Simon, F.; Tittmann, P; 和 Trinks, M. "支配多项式的递推关系和分裂公式。" Electron. J. Combin. 19, No. 3, Paper 47, 27 pp., 2012. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p47.Mertens, S. "网格、圆柱、环面和国王图的支配多项式。" 2024 年 8 月 15 日. https://arxiv.org/abs/2408.08053.van Rooij, J. M. M. 和 Bodlaender, H. L. "支配集的精确算法。" Discr. Appl. Math. 159, 2147-2164, 2011.

请引用为

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

主题分类