A126149 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A126149

Number of connected nonhamiltonian graphs with n nodes.

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

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-2019.

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 not-necessarily-connected simple nonhamiltonian graphs on n nodes).

Sequence in context: A151987 A369796 A356485 * 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