

A126149


Number of connected nonhamiltonian graphs with n nodes.


1



0, 1, 1, 3, 13, 64, 470, 4921, 83997, 2411453, 123544541, 11537642646, 2013389528672
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


REFERENCES

J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th SE Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259271.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 219.


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


FORMULA

a(n) = A001349(n)  A003216(n).


EXAMPLE

a(10) = A001349(10)  A003216(10) = number of connected graphs on 10 unlabeled nodes  number of Hamiltonian graphs with 10 nodes = 11716571  9305118 = 2411453.
a(11) = A001349(11)  A003216(11) = number of connected graphs on 11 unlabeled nodes  number of Hamiltonian graphs with 11 nodes = 1006700565  883156024 = 123544541.


CROSSREFS

Cf. A000088, A001349, A003216, A022564.
Cf. A246446 (number of notnecessarilyconnected simple nonhamiltonian graphs on n nodes).
Sequence in context: A065065 A020086 A151987 * A060927 A074537 A284714
Adjacent sequences: A126146 A126147 A126148 * A126150 A126151 A126152


KEYWORD

nonn,more


AUTHOR

Jonathan Vos Post, Mar 07 2007


EXTENSIONS

Terms a(1)a(9) corrected by Travis Hoppe, Jun 01 2014
a(11) added by Eric W. Weisstein, Aug 26 2014
a(12) from formula by Falk Hüffner, Aug 13 2017
a(13) added by Jan Goedgebeur, May 07 2019


STATUS

approved



