login
This site is supported by donations 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. 1
4, 6, 10, 14, 16, 18, 20, 22, 24, 26, 26, 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

LINKS

Table of n, a(n) for n=0..11.

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

Ed Pegg, Jr., Heawood graph shown with crossing number 3 and more symmetrically

Eric Weisstein, Graph Crossing Number

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) = a(10) = 26 from the McGee graph + edge (and unknown others).

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

CROSSREFS

Sequence in context: A084997 A300912 A175706 * A224467 A134624 A171945

Adjacent sequences:  A110504 A110505 A110506 * A110508 A110509 A110510

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 20 12:37 EST 2018. Contains 317402 sequences. (Running on oeis4.)