最小的三次图,其图的交叉数 ,已被 Pegg 和 Exoo (2009) 称为“交叉数图”或
-交叉图。
这些 -交叉图在 Wolfram 语言中实现为GraphData["CrossingNumberGraphNA"],其中N是一个数字,而X是一个字母,例如3C对于 Heawood 图,或8B对于 三次对称图
。
下表总结并更新了具有给定交叉数的最小三次图,修正了 Pegg 和 Exoo (2009) 的错误,并省略了三个未命名的 24 节点图中的两个(CNG 8D 和 CNG 8E),它们被错误地标记为交叉数 8(但实际上交叉数为 7),并注意到这里称为 CNG 9A 并标记为 “McGee + 边”(对应于 McGee 图中两个确定的边插入之一)的 26 节点图实际上具有 (不是 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)。
对于此表中的所有图,似乎 。
对于 = 0, 1, 2, ...,存在 1, 1, 2, 8, 2, 2, 3, 4, 3, ... (OEIS A307450) 个不同的交叉数图(修正了 Pegg 和 Exoo 2009),如上所示。交叉数为
, 1, ... 的最小三次图中的节点数为 4, 6, 10, 14, 16, 18, 20, 22, 24, 26, 28, 28, 30?, 30?, ... (OEIS A110507)。
计数 | |||
0 | 4 | 1 | 四面体图 |
1 | 6 | 1 | 效用图 |
2 | 10 | 2 | Petersen 图, CNG 2B |
3 | 14 | 8 | Heawood 图, |
4 | 16 | 2 | Möbius-Kantor 图, 8-交叉棱柱图 |
5 | 18 | 2 | Pappus 图, CNG 5B |
6 | 20 | 3 | Desargues 图, CNG 6B, CNG 6C |
7 | 22 | 4 | CNG 7A, CNG 7B, CNG 7C, CNG 7 D |
8 | 24 | 3 | McGee 图, Nauru 图, CNG 8C |
9 | 26 | 3? | |
10 | 28 | 2? | CNG 10A (McGee + 双边插入), CNG 10B |
11 | 28 | 1? | Coxeter 图 |
12 | 30? | 1? | CNG 12A (CNG 10A + 边插入) |
13 | 30? | 1? | Tutte 8-笼 |
14 | 36? | 1? | |
15 | 40? | 1? |
Clancy 等人 (2019) 证明了交叉数 11 的最小三次图是 Coxeter 图,肯定了 Pegg 和 Exoo (2009) 的一个猜想。