TOPICS
Search

Smallest Cubic Crossing Number Graph


SmallestCubicCrossingNumberGraphs

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

The n-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 F_(024)A.

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 CN(G)=RCN(G)=9 (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 Tutte 8-cage 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 CN(G)=RCN(G).

For n = 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 n=0, 1, ... are 4, 6, 10, 14, 16, 18, 20, 22, 24, 26, 28, 28, 30?, 30?, ... (OEIS A110507).

CN(G)V(G)countG
041tetrahedral graph K_4
161utility graph K_(3,3)
2102Petersen graph, CNG 2B
3148Heawood graph, GP(7,2), CNG 3A, CNG 3B, CNG 3D, CNG 3E, CNG 3F, CNG 3H
4162Möbius-Kantor graph, 8-crossed prism graph
5182Pappus graph, CNG 5B
6203Desargues graph, CNG 6B, CNG 6C
7224CNG 7A, CNG 7B, CNG 7C, CNG 7 D
8243McGee graph, Nauru graph, CNG 8C
9263?GP(13,5), CNG 9A (McGee + edge insertion), CNG 9B (edge-excised Coxeter)
10282?CNG 10A (McGee + double edge insertion), CNG 10B
11281?Coxeter graph
1230?1?CNG 12A (CNG 10A + edge insertion)
1330?1?Tutte 8-cage
1436?1?GP(18,5)
1540?1?GP(20,8)

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).


See also

Cubic Graph, Graph Crossing Number, Rectilinear Crossing Number

Explore with Wolfram|Alpha

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."

Cite this as:

Weisstein, Eric W. "Smallest Cubic Crossing Number Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SmallestCubicCrossingNumberGraph.html

Subject classifications