主题
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 的顶点图

使用 探索

参考文献

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. "顶点图。" 出自 Web 资源。 https://mathworld.net.cn/ApexGraph.html

主题分类