A003216 Number of Hamiltonian graphs with n nodes.

1, 0, 1, 3, 8, 48, 383, 6196, 177083, 9305118, 883156024, 152522187830, 48322518340547

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• hard
• more

Comments

a(1) could also be taken to be 0, but I prefer a(1) = 1. - N. J. A. Sloane, Oct 15 2006

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.
• R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• John Asplund, N. Bradley Fox, and Arran Hamm, New Perspectives on Neighborhood-Prime Labelings of Graphs, arXiv:1804.02473 [math.CO], 2018.
• J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)
• Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, preprint, 2015.
• Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, arXiv:1505.06508 [math.CO], 2015.
• Jan Goedgebeur, Barbara Meersman, and Carol T. Zamfirescu, Graphs with few Hamiltonian Cycles, arXiv:1812.05650 [math.CO], 2018-2019.
• Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
• Eric Weisstein's World of Mathematics, Hamiltonian Cycle
• Eric Weisstein's World of Mathematics, Hamiltonian Graph
• Wikipedia, Hamiltonian path
• Gus Wiseman, Non-isomorphic representatives of the a(5) = 8 simple graphs containing a Hamiltonian cycle.

Crossrefs

Main diagonal of A325455 and of A325447 (for n>=3).

The labeled case is A326208.

The directed case is A326226 (with loops) or A326225 (without loops).

The case without loops is A326215.

Unlabeled simple graphs not containing a Hamiltonian cycle are A246446.

Unlabeled simple graphs containing a Hamiltonian path are A057864.

Cf. A000088, A006125, A283420.

Formula

A000088(n) = a(n) + A246446(n). - Gus Wiseman, Jun 17 2019

Extensions

Extended to n=11 by Brendan McKay, Jul 15 1996

a(12) from Sean A. Irvine, Mar 17 2015

a(13) from A246446 added by Jan Goedgebeur, Sep 07 2019