login
The OEIS is supported by the many generous donors to the OEIS 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
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. A246446 (number of not-necessarily-connected simple nonhamiltonian graphs on n nodes).
Sequence in context: A151987 A369796 A356485 * A060927 A074537 A284714
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:22 EDT 2024. Contains 370952 sequences. (Running on oeis4.)