A smallest cubic crossing number graph is a finite, simple, connected cubic graph
of positive order whose vertex
count is minimum among such graphs with the same graph crossing number. Pegg and Exoo (2009)
termed these graphs "crossing number graphs"
or 
-crossing
graphs, where 
is their graph crossing
number.
Some smallest cubic crossing number graphs are also transmission-minimal regular graphs.
The numbers of 
-vertex connected cubic graphs having 0, 1, ... crossings for 
, 2, ... are given by
 |
(OEIS A390643).
The following table summarizes and updates the smallest cubic graphs having given graph crossing number,
correcting Pegg and Exoo (2009) 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 9B. 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.
2020) 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. 2020).
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 graph 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 7D |
| 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? | Tutte 8-cage |
| 14 | 36? | 1? |  |
| 15 | 40? | 1? |  |
Clancy et al. (2020) proved that the Coxeter graph is a smallest cubic graph with graph crossing number 11, settling in the affirmative a conjecture of Pegg and Exoo (2009). They also refuted the conjecture that the minimum order for graph crossing number 10 is 26, proving that it is 28.
