

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] (* JeanFranç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



