主题
Search

顶点图


顶点图是至少存在一个顶点,移除该顶点后得到的图是平面图的图。移除后得到平面图的顶点集合被称为该图的顶点集。

平面图因此是平凡顶点图,其所有顶点都是顶点集。

非平面顶点图,有时也称为近平面图(尽管此术语也在其他语境中使用),是至少存在一个顶点,移除该顶点后得到的图是平面图非平面图

顶点图与临界非平面图的区别在于,顶点图仅要求存在至少一个顶点,移除该顶点后得到平面图,而临界非平面图则要求移除每个顶点后都得到平面图

存在不是单交叉图的非平面顶点图。例如,完全二部图 K_(3,4) 是非平面的顶点图,但具有图交叉数 2。

每个顶点图的色数 <=5

NonplanarApexGraphs

顶点数为 n=1, 2, ... 的顶点图的数量分别为 1, 2, 4, 11, 34, 155, 1026, 11666, 226916, ... (OEIS A215620),而非平面顶点图的数量分别为 0, 0, 0, 0, 1, 13, 204, 4700, 147063, ... (OEIS A215621),其中顶点数 n<=5 的唯一非平面顶点图是完全图 K_5。上面展示了六个顶点的 13 个非平面顶点图。在这些图中,顶点集包括 (6,5)-图兰图 的除 1 和 2 之外的所有顶点,(6,132), (6,138), (6,148)(5,1)-棒棒糖图 的除顶点 2 之外的所有顶点,以及其他每个图的所有顶点。

根据Robertson-Seymour 定理,由于顶点图在子图运算下封闭,它们具有由禁忌子图组成的有限障碍集。顶点图的禁忌子图包括Petersen 族图以及 2K_5, K_5 union K_(3,3)2K_(3,3) 的不相交并集 (Pierce 2014, p. 8; Thomas 2014)。Pierce (2014) 确定了 157 个极小顶点禁忌子图,但禁忌子图的完整列表尚不清楚 (Gupta and Impagliazzo 1991, Pierce 2014)。

顶点图的Hadwiger 数最多为 5,因为它们包括禁忌子图中的完全图 K_6


另请参阅

顶点, 临界非平面图, 图偏斜度, 平面图, Robertson 的顶点图

使用 Wolfram|Alpha 探索

参考文献

Gupta, A. and Impagliazzo, R. "Computing Planar Intertwines." In Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91). IEEE Computer Society, pp. 802-811, 1991.Pierce, M. "Searching for and Classifying the Finite Set of Minor-Minimal Non-Apex Graphs." Honors thesis. Chico, CA: California State University, Chico, 2014. http://tmattman.yourweb.csuchico.edu/mpthesis.pdf.Sloane, N. J. A. Sequences A215620 and A215621 in "The On-Line Encyclopedia of Integer Sequences."Thomas, J. "Properties of 2-Connected MMNA Graphs." Preprint, 2014.

请引用本文为

Weisstein, Eric W. "顶点图。" 出自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/ApexGraph.html

主题分类