主題
Search

良覆蓋圖


良覆蓋圖是指每個極小頂點覆蓋都具有相同大小的圖,這等價於每個極大獨立頂點集都具有相同大小。 這也等價於每個極大獨立頂點集都是一個最大獨立頂點集,或者換句話說,極大和最大獨立頂點集的集合是相等的。 最後,良覆蓋性等價於下獨立數和(上)獨立數的相等。

良覆蓋圖族包括

1. Andásfai 圖,

2. 啞鈴圖,

3. 蜈蚣圖,

4. 雞尾酒會圖,

5. 完全圖 K_n,

6. 完全二部圖 K_(n,n).

7. 圈補圖 C^__n,

8. 梯子橫檔圖 nP_2,

9. 路徑補圖 P^__n,

10. 車圖 K_m square K_n,

11. 太陽花圖,

12. 三角形圖,

12. 三角形蜂巢車圖。

通常很容易透過簡單地找到兩個長度不同的極大獨立頂點集來識別非良覆蓋圖。 證明一個圖良覆蓋圖似乎更困難。

WellCoveredGraph

節點數為 n=1, 2, ... 的良覆蓋圖的數量是 1, 2, 3, 7, 14, 46, 164, 996, 10195, 208168, ... (OEIS A222626),其中前幾個在上面進行了說明。

WellCoveredConnectedGraph

節點數為 n=1, 2, ... 的連通良覆蓋圖的數量是 1, 1, 1, 3, 6, 27, 108, 788, 9035, 196928, ... (OEIS A222625),其中前幾個在上面進行了說明。


另請參閱

下獨立數, 極大獨立頂點集, 最大獨立頂點集

使用 探索

參考文獻

Plummer, M. D. "Some Covering Concepts in Graphs." J. Combin. Th. 8, 91-98, 1970.Sloane, N. J. A. Sequences A222625A222626 in "The On-Line Encyclopedia of Integer Sequences."

引用為

Weisstein, Eric W. "良覆蓋圖。" 來自 Web 資源。 https://mathworld.tw/Well-CoveredGraph.html