login
A246446
Number of nonhamiltonian graphs with n nodes.
12
0, 2, 3, 8, 26, 108, 661, 6150, 97585, 2700050, 135841840, 12568984762, 2179513027405
OFFSET
1,2
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
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.
Sequence in context: A358280 A343438 A107704 * A296093 A041399 A183948
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