最小的三次圖,其圖的交叉數 ,已被 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) 的一個猜想。