login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%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