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 的数量始终为偶数。