login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A110507 Number of nodes in the smallest cubic graph with crossing number n. 2
4, 6, 10, 14, 16, 18, 20, 22, 24, 26, 28, 28 (list; graph; refs; listen; history; text; internal format)
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
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.
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
Cf. A307450.
Sequence in context: A084997 A300912 A175706 * A224467 A134624 A171945
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 19 15:09 EDT 2024. Contains 373503 sequences. (Running on oeis4.)