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

另請參閱

點色數, 點色劃分, 支配集, 支配數, 上支配數

使用 探索

參考文獻

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. "支配多項式。" 來自 Web 資源。 https://mathworld.tw/DominationPolynomial.html

主題分類