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


另请参阅

图补图, 路径图, 串并联图, 串并联网络

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

Cograph

请引用为

Weisstein, Eric W. "Cograph。" 来自 MathWorld——Wolfram 网络资源。 https://mathworld.net.cn/Cograph.html

学科分类