Cograph(或“補可約圖”)是根據以下標準定義的簡單圖
1. 是一個 cograph,
2. 如果 是一個 cograph,那麼它的 圖補圖 也是,並且
3. 如果 和
是 cographs,那麼它們的 圖並
也是
(Brandstadt 等人,1999 年)。
請注意,自 1970 年代以來,cographs 已被多次獨立發現,因此不應將任何特定的定義或術語視為標準。Brandstadt 等人(1999 年)包含了許多關於 cographs 的獨立發現/定義/表徵的參考文獻。
一個圖 是一個 cograph,當且僅當以下任何等效條件成立時:
1. 可以透過不相交併和 圖連線 操作從孤立頂點構造出來。
2. 是直徑至多為 2 的距離遺傳圖的不相交併。
3. 在 的每個 匯出子圖
中,任何 極大團 和任何 最大獨立頂點集 的交集恰好包含一個頂點。
4. 的每個非平凡子圖都至少有一對雙胞胎(即,具有相同鄰域的兩個頂點)。
5. 的每個非平凡連通子圖的 圖補圖 都是不連通的。
6. 的每個連通子圖的直徑至多為 2。
節點數為 、2、... 的 cographs 的數量是 1、2、4、10、24、66、180、522、1532、...(OEIS A000084)。Brandstadt 等人(1999 年,定義 1.5)指出,如果一個圖的模組分解樹僅包含並行和序列節點,則該圖是一個 cograph。更具體和明確地說,節點數為
的 cographs 的計數與具有
個未標記邊的 串並聯網路 的計數相同,正如 Weisstein(2003ab)所指出並由 Sloane 證明的那樣。上面展示了節點數為
到 5 的前幾個 cographs。對於
,cographs 的數量始終為偶數。