菜单 主题
Search

最小三次交叉数图


SmallestCubicCrossingNumberGraphs

最小的三次图,其图的交叉数 CN(G)=n,已被 Pegg 和 Exoo (2009) 称为“交叉数图”或 n-交叉图。

这些 n-交叉图在 Wolfram 语言中实现为GraphData["CrossingNumberGraphNA"],其中N是一个数字,而X是一个字母,例如3C对于 Heawood 图,或8B对于 三次对称图 F_(024)A

下表总结并更新了具有给定交叉数的最小三次图,修正了 Pegg 和 Exoo (2009) 的错误,并省略了三个未命名的 24 节点图中的两个(CNG 8D 和 CNG 8E),它们被错误地标记为交叉数 8(但实际上交叉数为 7),并注意到这里称为 CNG 9A 并标记为 “McGee + 边”(对应于 McGee 图中两个确定的边插入之一)的 26 节点图实际上具有 CN(G)=RCN(G)=9 (不是 10),并添加了边删除的 Coxeter 图作为 CNG 9 B。此外,添加了交叉数为 10 的 28 节点图 CNG 10A(对应于 McGee 图中的双边插入或 Ed Pegg 于 2019 年 4 月 5 日构建的 Tutte 8-笼的边删除)和 CNG 10B(来自 Clancy等人 2019),以及 M. Haythorpe 在 2019 年 4 月 10 日左右告知 E. Pegg 的交叉数为 12 的 30 节点图 CNG 12A,它可以构建为 CNG 10A 上八个可能的边插入之一(Clancy等人 2019)。

对于此表中的所有图,似乎 CN(G)=RCN(G)

对于 n = 0, 1, 2, ...,存在 1, 1, 2, 8, 2, 2, 3, 4, 3, ... (OEIS A307450) 个不同的交叉数图(修正了 Pegg 和 Exoo 2009),如上所示。交叉数为 n=0, 1, ... 的最小三次图中的节点数为 4, 6, 10, 14, 16, 18, 20, 22, 24, 26, 28, 28, 30?, 30?, ... (OEIS A110507)。

CN(G)V(G)计数G
041四面体图 K_4
161效用图 K_(3,3)
2102Petersen 图, CNG 2B
3148Heawood 图, GP(7,2), CNG 3A, CNG 3B, CNG 3D, CNG 3E, CNG 3F, CNG 3H
4162Möbius-Kantor 图, 8-交叉棱柱图
5182Pappus 图, CNG 5B
6203Desargues 图, CNG 6B, CNG 6C
7224CNG 7A, CNG 7B, CNG 7C, CNG 7 D
8243McGee 图, Nauru 图, CNG 8C
9263?GP(13,5), CNG 9A (McGee + 边插入), CNG 9B (边删除的 Coxeter)
10282?CNG 10A (McGee + 双边插入), CNG 10B
11281?Coxeter 图
1230?1?CNG 12A (CNG 10A + 边插入)
1330?1?Tutte 8-笼
1436?1?GP(18,5)
1540?1?GP(20,8)

Clancy 等人 (2019) 证明了交叉数 11 的最小三次图是 Coxeter 图,肯定了 Pegg 和 Exoo (2009) 的一个猜想。


另请参阅

三次图, 图的交叉数, 直线交叉数

使用 探索

参考文献

Clancy, K.; Haythorpe, M.; Newcombe, A.; and Pegg, E. Jr. "There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11." Preprint. 2019.Pegg, E. Jr. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 161-170, 2009. https://www.mathematica-journal.com/data/uploads/2009/11/CrossingNumberGraphs.pdf.Sloane, N. J. A. Sequences A110507A307450 in "The On-Line Encyclopedia of Integer Sequences."

引用为

Weisstein, Eric W. “最小三次交叉数图。” 来自 ——Wolfram 网络资源。 https://mathworld.net.cn/SmallestCubicCrossingNumberGraph.html

主题分类