Smallest Cubic Crossing Number Graph

 

The smallest cubic graphs with graph crossing number  have been termed "crossing number graphs" or -crossing graphs by Pegg and Exoo (2009).

The -crossing graphs are implemented in the Wolfram Language as GraphData["CrossingNumberGraphNA"], with N being a number and X a letter, for example 3C for the Heawood graph or 8B for cubic symmetric graph .

The following table summarizes and updates the smallest cubic graphs having given crossing number, correcting Pegg and Exoo (2009) by and by omitting two of the three unnamed 24-node graphs (CNG 8D and CNG 8E) given as having crossing number 8 (but which actually have crossing number 7), noting that the 26-node graph here called CNG 9A and labeled as "McGee + edge" (corresponding to one of two certain edge insertions in the McGee graph) actually has  (not 10), and adding the edge-excised Coxeter graph as CNG 9 B. In addition, the 28-node graphs CNG 10A with crossing number 10 (corresponding to a double edge insertion in the McGee graph or edge excision from the Levi graph as constructed by Ed Pegg on Apr. 5, 2019) and CNG 10B (from Clancy et al. 2019) are added, as is the 30-node graph CNG 12A with crossing number 12 communicated by M. Haythorpe to E. Pegg on or around Apr. 10, 2019 which is constructible as one of eight possible edge insertions on CNG 10A (Clancy et al. 2019).

For all graphs in this table, it appears that .

For  = 0, 1, 2, ..., there are 1, 1, 2, 8, 2, 2, 3, 4, 3, ... (OEIS A307450) distinct crossing number graphs (correcting Pegg and Exoo 2009), illustrated above. The number of nodes in the smallest cubic graph with crossing number , 1, ... are 4, 6, 10, 14, 16, 18, 20, 22, 24, 26, 28, 28, 30?, 30?, ... (OEIS A110507).

		count
0	4	1	tetrahedral graph
1	6	1	utility graph
2	10	2	Petersen graph, CNG 2B
3	14	8	Heawood graph, , CNG 3A, CNG 3B, CNG 3D, CNG 3E, CNG 3F, CNG 3H
4	16	2	Möbius-Kantor graph, 8-crossed prism graph
5	18	2	Pappus graph, CNG 5B
6	20	3	Desargues graph, CNG 6B, CNG 6C
7	22	4	CNG 7A, CNG 7B, CNG 7C, CNG 7 D
8	24	3	McGee graph, Nauru graph, CNG 8C
9	26	3?	, CNG 9A (McGee + edge insertion), CNG 9B (edge-excised Coxeter)
10	28	2?	CNG 10A (McGee + double edge insertion), CNG 10B
11	28	1?	Coxeter graph
12	30?	1?	CNG 12A (CNG 10A + edge insertion)
13	30?	1?	Levi graph
14	36?	1?
15	40?	1?

Clancy et al. (2019) proved that the smallest cubic graph with graph crossing number 11 is the Coxeter graph, settling in the affirmative a conjecture of Pegg and Exoo (2009).

---

REFERENCES

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 A110507 and A307450 in "The On-Line Encyclopedia of Integer Sequences."

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength