選單 主題
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.tw/SmallestCubicCrossingNumberGraph.html

主題分類