主題
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 貢獻

使用 探索

參考文獻

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.

在 中引用

支配數

請引用本文為

Bray, Nicolas and Weisstein, Eric W. "支配數。" 來自 —— 資源。 https://mathworld.tw/DominationNumber.html

學科分類