login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A246446 Number of nonhamiltonian graphs with n nodes. 12
0, 2, 3, 8, 26, 108, 661, 6150, 97585, 2700050, 135841840, 12568984762, 2179513027405 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

LINKS

Table of n, a(n) for n=1..13.

Jan Goedgebeur, Barbara Meersman, Carol T. Zamfirescu, Graphs with few Hamiltonian Cycles, arXiv:1812.05650 [math.CO], 2018.

Eric Weisstein's World of Mathematics, Nonhamiltonian Graph

Wikipedia, Hamiltonian path

FORMULA

a(n) = A000088(n) - A003216(n).

MATHEMATICA

A000088 = Cases[Import["https://oeis.org/A000088/b000088.txt", "Table"], {_, _}][[All, 2]];

A003216 = Cases[Import["https://oeis.org/A003216/b003216.txt", "Table"], {_, _}][[All, 2]];

a[n_] := A000088[[n + 1]] - A003216[[n]];

a /@ Range[13] (* Jean-François Alcover, Jan 02 2020 *)

CROSSREFS

Cf. A000088 (number of simple graphs on n nodes).

Cf. A003216 (number of Hamiltonian graphs on n nodes).

Cf. A126149 (number of connected nonhamiltonian graphs on n nodes).

The labeled case is A326207.

The directed case is A326223 (with loops) or A326222 (without loops).

Unlabeled simple graphs not containing a Hamiltonian path are A283420.

Cf. A006125, A057864, A326205, A326206.

Sequence in context: A065619 A111121 A107704 * A296093 A041399 A183948

Adjacent sequences:  A246443 A246444 A246445 * A246447 A246448 A246449

KEYWORD

nonn,more

AUTHOR

Eric W. Weisstein, Aug 26 2014

EXTENSIONS

a(12) from formula by Falk Hüffner, Aug 13 2017

a(13) added by Jan Goedgebeur, May 07 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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 07:59 EST 2020. Contains 331081 sequences. (Running on oeis4.)