login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 23 06:50 EST 2020. Contains 332159 sequences. (Running on oeis4.)