A246446 Number of nonhamiltonian graphs with n nodes.

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

Offset: 1

Author

Eric W. Weisstein, Aug 26 2014

Keywords

• nonn
• more

Links

• 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

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.

Programs

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 *)

Formula

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

Extensions

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

a(13) added by Jan Goedgebeur, May 07 2019