A126149 Number of connected nonhamiltonian graphs with n nodes.

0, 1, 1, 3, 13, 64, 470, 4921, 83997, 2411453, 123544541, 11537642646, 2013389528672

Offset: 1

Author

Jonathan Vos Post, Mar 07 2007

Keywords

• nonn
• more

Examples

			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.
		

References

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

Links

• Jan Goedgebeur, Barbara Meersman, Carol T. Zamfirescu, Graphs with few Hamiltonian Cycles, arXiv:1812.05650 [math.CO], 2018-2019.
• Eric Weisstein's World of Mathematics, Nonhamiltonian Graph.

Crossrefs

Cf. A000088, A001349, A003216, A022564.

Cf. A246446 (number of not-necessarily-connected simple nonhamiltonian graphs on n nodes).

Formula

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

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