OFFSET
0,1
COMMENTS
The Coxeter graph on 28 vertices needs 11 crossings and the Levi graph on 30 requires 13.
Haythorpe and Newcombe prove that a(11) > 26 and thus that a(11) = 28. - Jeremy Tan, Apr 30 2018
Clancy, Haythorpe, and Newcombe prove in a 2019 preprint that there are no cubic graphs on 26 vertices with crossing number 10. - Eric W. Weisstein, Apr 07 2019
LINKS
A. E. Brouwer, The Heawood Graph
Geoff Exoo, Rectlinear Drawings of Famous Graphs
Michael Haythorpe and Alex Newcombe, There are no Cubic Graphs on 26 Vertices with Crossing Number 11, arXiv preprint arXiv:1804.10336 [math.CO], 2018.
Ed Pegg, Jr., Cubic Symmetric Graphs
Ed Pegg, Jr., Cubic Symmetric Graphs
Eric Weisstein's World of Mathematics, Smallest Cubic Crossing Number Graph
EXAMPLE
a(0) = 4 from the complete graph K_4.
a(1) = 6 from the utility graph K_{3,3}.
a(2) = 10 from the Petersen graph (and 1 other).
a(3) = 14 from the Heawood graph (and 7 others).
a(4) = 16 from the Moebius-Kantor graph (and 1 other).
a(5) = 18 from the Pappus graph (and 1 other).
a(6) = 20 from the Desargues graph (and 2 others based on 10_3 configurations).
a(7) = 22 from the 7-crossing graphs (4 in total).
a(8) = 24 from the McGee graph (and 3 others).
a(9) = 26 from the McGee graph + edge insertion and edge-excised Coxeter graph (and unknown others).
a(10) = 28 from the McGee graph + double edge insertion and another from Clancy et al. preprint (and unknown others).
a(11) = 28 from the Coxeter graph (and unknown others).
a(12) <= 30 from the CNG 10A + edge insertion.
a(13) <= 30 from the Levi graph.
a(14) <= 36 from GP(18,5). - Eric W. Weisstein, Apr 15 2019
a(15) <= 40 from GP(20,8). - Eric W. Weisstein, Apr 15 2019
CROSSREFS
KEYWORD
nonn,more
AUTHOR
N. J. A. Sloane, based on email from Ed Pegg Jr, Mar 14 2007, Mar 16 2007, Jan 28 2009
EXTENSIONS
a(11) added and offset corrected by Jeremy Tan, Apr 30 2018
a(10) corrected (McGee graph + insertion has CN = 9, not 10) by Eric W. Weisstein, Apr 05 2019
STATUS
approved