主题
Search

支配数

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
DominatingSet

图 G 的（下）支配数 gamma(G) 是 支配集 中顶点的最小数量，也就是 最小支配集 的大小。这等价于 极小支配集 的最小大小，因为每个 最小支配集 也是极小的。支配数也等于 支配多项式 中的最小指数。例如，在上面图示的 Petersen 图 P 中，集合 S={1,2,9} 是一个 最小支配集，因此 gamma(P)=3。

上支配数 Gamma(G) 可以类似地定义为 极小支配集 中顶点的最大大小，图 G (Burger et al. 1997, Mynhardt and Roux 2020)。

（下）冗余数 ir(G)、下支配数 gamma(G)、下独立数 i(G)、上独立数 alpha(G)、上支配数 Gamma(G) 和 上冗余数 IR(G) 满足以下不等式链

ir(G)<=gamma(G)<=i(G)<=alpha(G)<=Gamma(G)<=IR(G)
(1)

(Burger et al. 1997)。

支配数不应与支配划分数混淆，后者是图中支配划分的最大大小。

支配数有几种变体，源于底层支配集的不同变体，最常见的是全支配数（它是全支配集的最小大小）。

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

完全图 K_n（每个顶点与所有其他顶点相邻）、星图 S_n（中心顶点与所有叶子相邻）和轮图 W_n（中心顶点与所有轮辋顶点相邻）根据构造都具有支配数 1。

支配数满足

n/(1+Delta)<=gamma<=n,
(2)

其中 n=|V| 是图的顶点计数，Delta 是其最大顶点度。

对于顶点计数为 n 且没有孤立顶点的图 G（即最小顶点度 delta(G)>=1），

gamma(G)<=1/2n
(3)

(Ore 1962, Bujtás 和 Klavžar 2014)。当 delta(G)=2、3 等时，已知更严格的结果（参见 Bujtás 和 Klavžar 2014）。

MacGillivray 和 Seyffarth (1996) 表明，平面图的图直径为 2 时，支配数最多为 3，平面图的图直径为 3 时，支配数最多为 10。Goddard 和 Henning (2002) 实际上表明，存在一个唯一的直径为 2 且支配数为 3 的平面图（此处称为 Goddard-Henning 图），所有其他此类图的支配数最多为 2。根据 Goddard 和 Henning (2002)，尚不清楚直径为 3 的平面图的界限是否是紧的，但 MacGillivray 和 Seyffarth (1996) 给出了一个支配数为 6 的此类图的例子。

全支配数 gamma_t 和普通支配数 gamma 满足

gamma<=gamma_t<=2gamma
(4)

(Henning 和 Yeo 2013, p. 17)。

Östergård et al. (2015) 给出了 Kneser 图 的支配数的界限，以及较小情况的一些精确值。

可以使用 Wolfram 语言 获得许多命名图的预计算支配集，方法是使用GraphData[graph,"DominationNumber"].

下表总结了各种特殊图类的支配数的值。

图 G_nOEISgamma(G_1), gamma(G_2), ...
Andrásfai 图A1587991, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, ...
阿波罗尼斯网络A0000001, 1, 3, 4, 7, 16, ...
反棱柱图A0573542, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, ...
哑铃图A0073952, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
书图 S_(n+1) square P_2A0073952, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
蜈蚣图A0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...
鸡尾酒会图 K_(n×2)A0073952, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
完全二部图 K_(m,n)A0073952, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
完全图 K_nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
完全三部图 K_(n,n,n)A0000001 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
2n-交叉棱柱图A052928X, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, ...
冠图A0073952, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
立方体连接环图A0000006, 16, 46, 96, 224, 512, ...
环图 C_nA002264X, X, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, ...
空图 K^__nA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...
折叠立方体图A2715201, 1, 2, 4, 6, 8, 16, 32, ...
网格图 P_n square P_nA1045192, 3, 4, 7, 10, 12, 16, 20, 24, ...
网格图 P_n square P_ square P_nA2697061, 2, 6, 15, 25, 42, ...
齿轮图A000000X, X, 2, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, ...
半立方体图A0000001, 1, 1, 2, 2, 2, 4, 7, 12, ...
舵图A000027X, X, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...
超立方体图 Q_nA0009831, 2, 2, 4, 7, 12, 16, 32, ...
Keller 图 G_nA0000004, 4, 4, 4, ...
n×n-国王图A0755611, 1, 1, 4, 4, 4, 9, 9, 9, 16, 16, 16, 25, 25, 25, 36, ...
n×n-骑士图A0060751, 4, 4, 4, 5, 8, 10, 12, 14, 16, 21, 24, 28, 32, 36, ...
梯子图 P_2 square P_nA0045261, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, ...
梯子横档图 nP_2A0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...
莫比乌斯梯子 M_nA004525X, X, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 7, 7, 8, 9, 9, 9, ...
Mycielski 图 M_nA0000001, 1, 2, 3, 4, 5, 6, 7, 8, ...
奇图 O_nA0000001, 1, 3, 7, 26, 66, ...
平底锅图A002264X, X, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, ...
路径图 P_nA002264X, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, ...
棱柱图 Y_nA004524X, X, 2, 2, 3, 4, 4, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 10, ...
n×n-皇后图A0754581, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 10, ...
谢尔宾斯基地毯图A0000003, 18, 130, ...
谢尔宾斯基垫片图A0000001, 2, 3, 9, 27, ...
星图 S_nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
太阳图A004526X, X, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, ...
小太阳图 C_n circledot K_1A000000
四面体约翰逊图A000000X, X, X, X, X, 2, 4, 5, 7, 8, ...
环面网格图 C_n square C_nA000000
转置图 G_nA0000001, 1, 2, 4, 15, ...
三角形图A0045262, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, ...
三角形蜂窝锐角骑士图A0000001, 3, 3, 3, 3, 6, 9, 9, 9, 10, 15, 18, 18, 18, ...
三角形蜂窝钝角骑士图A251534X, X, X, 4, 5, 5, 6, 6, 9, 11, 12, 14, 15, 16, 18, 19, ...
三角形蜂窝皇后图A0000001, 1, 2, 2, 3, 3, 3, 4, 4, 5, ...
三角形蜂窝车图A0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
网状图A000027X, X, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
轮图 W_nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

封闭形式总结在下表中。

图 G_ngamma(G_n)
Andrásfai 图{1 for n=1; 2 for n=2; 3 otherwise
反棱柱图|_(2(n+2))/5_|
阿波罗尼斯网络{1 for n=1,2; 1/2(3^(n-3)+5) otherwise
哑铃图2
书图 S_(n+1) square P_22
蜈蚣图n
鸡尾酒会图 K_(n×2)2
完全图 K_n1
完全二部图 K_(m,n)2
完全三部图 K_(k,m,n){1 for k=1; 2 otherwise
2n-交叉棱柱图2|_(n+1)/2_|
冠图2
环图 C_n|_(n+2)/3_|
空图 K^__nn
齿轮图{2 for n=3; |_(n+2)/2_| otherwise
网格图 P_n square P_n{n for n<=4; 7 for n=5; 10 for n=6; 40 for n=13; |_((n+2)^2)/5_|-4 otherwise
舵图n
Keller 图 G_n4
m×n 国王图|_(m+2)/3_||_(n+2)/3_|
梯子图 P_2 square P_n1+|_n/2_|
梯子横档图 nP_2n
莫比乌斯梯子 M_n|_(n+1)/4_|+[(n+1)/4]
平底锅图|_(n+2)/3_|
路径图 P_n|_(n+2)/3_|
棱柱图 Y_n|_(n+2)/4_|+|_(n+3)/4_|
m×n 车图min(m,n)
星图 S_n1
太阳图|_(n+1)/2_|
三角形图|_n/2_|
三角形蜂窝车图n
网状图n
轮图 W_n1

另请参阅

连通支配数, 支配划分数, 支配划分, 支配性, 支配多项式, 支配集, 最小支配集, 全支配数, 上支配数, 维辛猜想

此条目的部分内容由 Nicolas Bray 贡献

使用 Wolfram|Alpha 探索

参考文献

Alikhani, S. and Peng, Y.-H. "Introduction to Domination Polynomial of a Graph." Ars Combin. 114, 257-266, 2014.Bujtás, C. and Klavžar, S. "Improved Upper Bounds on the Domination Number of Graphs with Minimum Degree at Least Five." 16 Oct 2014. https://arxiv.org/abs/1410.4334.Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.Clark, W. E. and Suen, S. "An Inequality Related to Vizing's Conjecture." Electronic J. Combinatorics 7, No. 1, N4, 1-3, 2000. http://www.combinatorics.org/Volume_7/Abstracts/v7i1n4.html.Cockayne, E. J. and Mynhardt, C. M. "The Sequence of Upper and Lower Domination, Independence and Irredundance Numbers of a Graph." Disc. Math. 122, 89-102, 1993).Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, p. 190, 1983.Goddard, W. Henning, M. A. "Domination in Planar Graphs with Small Diameter." J. Graph Th. 40, 1-25, 2002.Haynes, T. W.; Hedetniemi, S. T.; and Slater, P. J. Domination in Graphs--Advanced Topics. New York: Dekker, 1998.Haynes, T. W.; Hedetniemi, S. T.; and Slater, P. J. Fundamentals of Domination in Graphs. New York: Dekker, 1998.Henning, M. A. and Yeo, A. Total Domination in Graphs. New York: Springer, 2013.MacGillivray, G. and Seyffarth, K. "Domination Numbers of Planar Graphs." J. Graph Th. 22, 213-219, 1996.Mertens, S. "Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph." 15 Aug 2024. https://arxiv.org/abs/2408.08053.Mynhardt, C. M. and Roux, A. "Irredundance Graphs." 14 Apr. 2020. https://arxiv.org/abs/1812.03382.Ore, O. Theory of Graphs. Providence, RI: Amer. Math. Soc., 1962.Östergård, P. R. J.; Shao, Z.; and Xu, X. "Bounds on the Domination Number of Kneser Graphs." Ars Math. Contemp. 9, 197-205, 2015.Sloane, N. J. A. Sequences A000012/M0003, A000027/M0472, A002264, A004524, A004525, A004526, A006075, A007395/M0208, A052928, A057354, A075458, A075561, A104519, A158799, A251534, A269706, and A271520 in "The On-Line Encyclopedia of Integer Sequences."van Rooij, J. M. M. and Bodlaender, H. L. "Exact Algorithms for Dominating Set." Discr. Appl. Math. 159, 2147-2164, 2011.

在 Wolfram|Alpha 中引用

支配数

请引用本文为

Bray, Nicolas and Weisstein, Eric W. "支配数。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/DominationNumber.html

学科分类