A110507 - OEIS

%I #44 Feb 16 2025 08:32:58

%S 4,6,10,14,16,18,20,22,24,26,28,28

%N Number of nodes in the smallest cubic graph with crossing number n.

%C The Coxeter graph on 28 vertices needs 11 crossings and the Levi graph on 30 requires 13.

%C Haythorpe and Newcombe prove that a(11) > 26 and thus that a(11) = 28. - _Jeremy Tan_, Apr 30 2018

%C 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

%H A. E. Brouwer, <a href="http://www.win.tue.nl/~aeb/drg/graphs/Heawood.html">The Heawood Graph</a>

%H Geoff Exoo, <a href="http://ginger.indstate.edu/ge/Graphs/RECTILINEAR/index.html">Rectlinear Drawings of Famous Graphs</a>

%H Michael Haythorpe and Alex Newcombe, <a href="https://arxiv.org/abs/1804.10336">There are no Cubic Graphs on 26 Vertices with Crossing Number 11</a>, arXiv preprint arXiv:1804.10336 [math.CO], 2018.

%H Ed Pegg, Jr., <a href="http://www.maa.org/editorial/mathgames/mathgames_12_29_03.html">Cubic Symmetric Graphs</a>

%H Ed Pegg, Jr., <a href="https://mathworld.wolfram.com/CubicSymmetricGraph.html">Cubic Symmetric Graphs</a>

%H Ed Pegg, Jr., <a href="/A110507/a110507.png">Heawood graph shown with crossing number 3 and more symmetrically</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SmallestCubicCrossingNumberGraph.html">Smallest Cubic Crossing Number Graph</a>

%e a(0) = 4 from the complete graph K_4.

%e a(1) = 6 from the utility graph K_{3,3}.

%e a(2) = 10 from the Petersen graph (and 1 other).

%e a(3) = 14 from the Heawood graph (and 7 others).

%e a(4) = 16 from the Moebius-Kantor graph (and 1 other).

%e a(5) = 18 from the Pappus graph (and 1 other).

%e a(6) = 20 from the Desargues graph (and 2 others based on 10_3 configurations).

%e a(7) = 22 from the 7-crossing graphs (4 in total).

%e a(8) = 24 from the McGee graph (and 3 others).

%e a(9) = 26 from the McGee graph + edge insertion and edge-excised Coxeter graph (and unknown others).

%e a(10) = 28 from the McGee graph + double edge insertion and another from Clancy et al. preprint (and unknown others).

%e a(11) = 28 from the Coxeter graph (and unknown others).

%e a(12) <= 30 from the CNG 10A + edge insertion.

%e a(13) <= 30 from the Levi graph.

%e a(14) <= 36 from GP(18,5). - _Eric W. Weisstein_, Apr 15 2019

%e a(15) <= 40 from GP(20,8). - _Eric W. Weisstein_, Apr 15 2019

%Y Cf. A307450.

%K nonn,more

%O 0,1

%A _N. J. A. Sloane_, based on email from _Ed Pegg Jr_, Mar 14 2007, Mar 16 2007, Jan 28 2009

%E a(11) added and offset corrected by _Jeremy Tan_, Apr 30 2018

%E a(10) corrected (McGee graph + insertion has CN = 9, not 10) by _Eric W. Weisstein_, Apr 05 2019