|
%I #43 May 14 2019 15:27:15
%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="http://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="http://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
| 