A246446 Number of nonhamiltonian graphs with n nodes.

0, 2, 3, 8, 26, 108, 661, 6150, 97585, 2700050, 135841840, 12568984762, 2179513027405

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: A358280 A343438 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