A003216 Number of Hamiltonian graphs with n nodes. (Formerly M2764)

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

Offset

1,4

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

Table of n, a(n) for n=1..13.

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.

Formula

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

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.

Sequence in context: A309578 A291504 A034183 * A366755 A146161 A304698

Adjacent sequences: A003213 A003214 A003215 * A003217 A003218 A003219

Keyword

nonn,nice,hard,more

Author

N. J. A. Sloane

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

Status

approved