主题
Search

单图图


单图图(或简称为“单图”)是与每个具有该度序列的图同构的图。所有顶点数为四个或更少的图都是单图图。

节点数为 n=1, 2, ... 的单图图的数量是 1, 2, 4, 11, 28, 72, 170, 407, 956, 2252 ... (OEIS A122423),其中连通图的数量是 1, 1, 2, 6, 16, 42, 96, 234, 546, 1292, ... (OEIS A365548)。在所有节点数为 n 的连通图中,具有不同度序列的连通图的数量,对于 n=1, 2, ... 是 1, 1, 1, 2, 6, 17, 45, 99, 238, 549, 1296, ... (OEIS A309757)。

因此,在 5 个顶点上有 6 个非单图图,包括路径图 P_5P_2+C_3,它们共享度序列 (2,2,2,1,1)

如果图 G 是单图图,则其图补图 G^_ 也是单图图 (Barrus et al. 2023)。

Kleitman (1975) 描述了一种用于在线性时间内识别单图性的算法。虽然单图类没有禁止的诱导子图表征,但可以通过分解来表征它 (Barrus et al. 2023)。 特别是,图 G 是单图图 当且仅当 其 Tyshkevich 分解的每个分量都是单图图 (Tyshkevich 2000, Barrus et al. 2023)。

唯一的正则单图图是完全图 K_n空图 K^__n梯子阶图 mK_2鸡尾酒会图 mK_2^_圈图 C_5 (Johnson 1975, Koren 1976, Tyshkevich 2000)。


另请参阅

度序列, 图序列, 顶点度

使用 Wolfram|Alpha 探索

参考文献

Barrus, M. D.; Trenk, A. N.; and Whitman, R. "The Hereditary Closure of the Unigraphs." 23 Aug 2023. https://arxiv.org/abs/2308.12190Johnson, R. H. "Simple Separable Graphs." Pacific J. Math. 56, 143-158, 1975.Kleitman, D. J. and Li, S.-Y. "A Note on Unigraphic Sequences." Stud. Appl. Math. 54, 283-287, 1975.Koren, M. "Pairs of Sequences with a Unique Realization by Bipartite Graphs." J. Combin. Th. Ser. B 21, 224-234, 1976.Koren, M. "Sequences with a Unique Realization by Simple Graphs." J. Combin. Th. Ser. B 21, 235-244, 1976.Li, S.-Y. R. "Graphic Sequences with Unique Realizations." J. Combin. Th. Ser. B 19, 42-68, 1975.Sloane, N. J. A. Sequences A122423, A309757, and A365548 in "The On-Line Encyclopedia of Integer Sequences."Tyshkevich, R. "The Canonical Decomposition of a Graph." Dokl. Akad. Nauk. BSSR 24, 677-679, 1980.Tyshkevich, R. "Decomposition of Graphical Sequences and Unigraphs." Disc. Math. 220, 201-238, 2000.

引用为

Weisstein, Eric W. "单图图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/UnigraphicGraph.html

主题分类