主題
Search

Cograph


Cograph(或“補可約圖”)是根據以下標準定義的簡單圖

1. K_1 是一個 cograph,

2. 如果 X 是一個 cograph,那麼它的 圖補圖 也是,並且

3. 如果 XY 是 cographs,那麼它們的 圖並 X union Y 也是

(Brandstadt 等人,1999 年)。

請注意,自 1970 年代以來,cographs 已被多次獨立發現,因此不應將任何特定的定義或術語視為標準。Brandstadt 等人(1999 年)包含了許多關於 cographs 的獨立發現/定義/表徵的參考文獻。

一個圖 G 是一個 cograph,當且僅當以下任何等效條件成立時:

1. G 可以透過不相交併和 圖連線 操作從孤立頂點構造出來。

2. G 是直徑至多為 2 的距離遺傳圖的不相交併。

3. 在 H 的每個 匯出子圖 G 中,任何 極大團 和任何 最大獨立頂點集 的交集恰好包含一個頂點。

4. G 的每個非平凡子圖都至少有一對雙胞胎(即,具有相同鄰域的兩個頂點)。

5. G 的每個非平凡連通子圖的 圖補圖 都是不連通的。

6. G 的每個連通子圖的直徑至多為 2。

7. G 不包含 路徑圖 P_4 作為 匯出子圖

Cographs

節點數為 n=1、2、... 的 cographs 的數量是 1、2、4、10、24、66、180、522、1532、...(OEIS A000084)。Brandstadt 等人(1999 年,定義 1.5)指出,如果一個圖的模組分解樹僅包含並行和序列節點,則該圖是一個 cograph。更具體和明確地說,節點數為 n 的 cographs 的計數與具有 n 個未標記邊的 串並聯網路 的計數相同,正如 Weisstein(2003ab)所指出並由 Sloane 證明的那樣。上面展示了節點數為 n=1 到 5 的前幾個 cographs。對於 n>1,cographs 的數量始終為偶數。


另請參閱

圖補圖, 路徑圖, 串並聯圖, 串並聯網路

使用 探索

參考文獻

Brandstadt, A.; Le, V. B.; Spinrad, J. P. 圖類:綜述。 Philadelphia, PA: SIAM, 1999.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. New York: Springer-Verlag, p. 435, 1989.Corneil, D. H.; Lerchs, H.; and Stewart Burlingham, L. "補可約圖。" Discr. Appl. Math. 3, 163-174, 1981.Sloane, N. J. A. 序列 A000084/M1207 in "The On-Line Encyclopedia of Integer Sequences."Weisstein, E. W. "關於:Cographs。" 2003年10月9日。 http://listserv.nodak.edu/scripts/wa.exe?A2=ind0310&L=graphnet&P=R743.Weisstein, E. W. "Cographs <=> 串並聯網路。" 2003年10月23日。 http://listserv.nodak.edu/scripts/wa.exe?A2=ind0310&L=graphnet&P=R1929.

在 中被引用

Cograph

請引用為

Weisstein, Eric W. "Cograph。" 來自 ——Wolfram 網路資源。 https://mathworld.tw/Cograph.html

學科分類