A283420 -id:A283420 - cp's OEIS frontend

A003216 Number of Hamiltonian graphs with n nodes.

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

Offset: 1

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

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

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.

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.

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

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

A057864 Number of simple traceable graphs on n nodes.

Original entry on oeis.org

1, 1, 2, 5, 18, 91, 734, 10030, 248427, 11482572, 1000231510

Offset: 1

Eric W. Weisstein

Number of undirected graphs on n nodes possessing a Hamiltonian path (not circuit).

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version f0eaa32.
Eric Weisstein's World of Mathematics, Traceable Graph
Wikipedia, Hamiltonian path
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.
Gus Wiseman, Non-isomorphic representatives of the a(5) = 18 unlabeled simple graphs containing a Hamiltonian path.

Main diagonal of A309524.
The labeled case is A326206.
The directed case is A326221 (with loops).
Unlabeled simple graphs not containing a Hamiltonian path are A283420.
Unlabeled simple graphs containing a Hamiltonian cycle are A003216.
Cf. A000088, A006125, A246446, A283420, A326205, A326217.

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

a(8) and a(9) from Eric W. Weisstein, Jun 04 2004
a(10) from Eric W. Weisstein, May 27 2009
a(11) added using tinygraph by Falk Hüffner, Jan 19 2016

A246446 Number of nonhamiltonian graphs with n nodes.

Original entry on oeis.org

0, 2, 3, 8, 26, 108, 661, 6150, 97585, 2700050, 135841840, 12568984762, 2179513027405

Offset: 1

Eric W. Weisstein, Aug 26 2014

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
Wikipedia, Hamiltonian path

Cf. A000088 (number of simple graphs on n nodes).
Cf. A003216 (number of Hamiltonian graphs on n nodes).
Cf. A126149 (number of connected nonhamiltonian graphs on n nodes).
The labeled case is A326207.
The directed case is A326223 (with loops) or A326222 (without loops).
Unlabeled simple graphs not containing a Hamiltonian path are A283420.
Cf. A006125, A057864, A326205, A326206.

A000088 = Cases[Import["https://oeis.org/A000088/b000088.txt", "Table"], {, }][[All, 2]];
A003216 = Cases[Import["https://oeis.org/A003216/b003216.txt", "Table"], {, }][[All, 2]];
a[n_] := A000088[[n + 1]] - A003216[[n]];
a /@ Range[13] (* Jean-François Alcover, Jan 02 2020 *)

a(n) = A000088(n) - A003216(n).

a(12) from formula by Falk Hüffner, Aug 13 2017

a(13) added by Jan Goedgebeur, May 07 2019

A326206 Number of n-vertex labeled simple graphs containing a Hamiltonian path.

Original entry on oeis.org

0, 0, 1, 4, 34, 633, 23368, 1699012, 237934760, 64558137140, 34126032806936, 35513501049012952

Offset: 0

Gus Wiseman, Jun 14 2019

A path is Hamiltonian if it passes through every vertex exactly once.

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 9766535.
Wikipedia, Hamiltonian path
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.
Gus Wiseman, The a(4) = 34 simple graphs containing a Hamiltonian path

The unlabeled case is A057864.
The directed case is A326214 (with loops) or A326217 (without loops).
Simple graphs without a Hamiltonian path are A326205.
Simple graphs with a Hamiltonian cycle are A326208.
Cf. A003216, A006125, A057864, A283420.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],FindHamiltonianPath[Graph[Range[n],#]]!={}&]],{n,0,4}] (* Mathematica 10.2+ *)

A006125(n) = a(n) + A326205(n).

a(7)-a(11) added using tinygraph by Falk Hüffner, Jun 21 2019

A326208 Number of Hamiltonian labeled simple graphs with n vertices.

Original entry on oeis.org

0, 1, 0, 1, 10, 218, 10078, 896756, 151676112, 47754337568, 28229412456056, 31665593711174080

Offset: 0

Gus Wiseman, Jun 15 2019

A graph is Hamiltonian if it contains a cycle passing through every vertex exactly once.

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 9766535.
Wikipedia, Hamiltonian path
Gus Wiseman, The a(5) = 218 simple graphs containing a Hamiltonian cycle.

The unlabeled version is A003216.
The directed version is A326204 (with loops) or A326219 (without loops).
Simple graphs not containing a Hamiltonian cycle are A326207.
Simple graphs containing a Hamiltonian path are A326206.
Cf. A003216, A006125, A057864, A283420.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],FindHamiltonianCycle[Graph[Range[n],#]]!={}&]],{n,0,4}] (* Mathematica 8.0+ *)

A006125(n) = a(n) + A326207(n).

a(7)-a(11) added using tinygraph by Falk Hüffner, Jun 21 2019

A326221 Number of unlabeled n-vertex digraphs (with loops) containing a Hamiltonian path.

Original entry on oeis.org

0, 0, 7, 74, 2395

Offset: 0

Gus Wiseman, Jun 16 2019

A directed path is Hamiltonian if it passes through every vertex exactly once.

Wikipedia, Hamiltonian path
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.
Gus Wiseman, Non-isomorphic representatives of the a(3) = 74 digraphs containing a Hamiltonian path.

The labeled case is A326214.
The undirected case is A057864 (without loops).
Unlabeled digraphs not containing a Hamiltonian path are A326224.
Unlabeled digraphs containing a Hamiltonian cycle are A326226.
Cf. A000595, A002416, A003087, A003216, A283420.

A000595(n) = a(n) + A326224(n).

A326224 Number of unlabeled n-vertex digraphs (with loops) not containing a Hamiltonian path.

Original entry on oeis.org

1, 2, 3, 30, 649

Offset: 0

Gus Wiseman, Jun 16 2019

A directed path is Hamiltonian if it passes through every vertex exactly once.

Wikipedia, Hamiltonian path
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.
Gus Wiseman, Non-isomorphic representatives of the a(3) = 30 digraphs not containing a Hamiltonian path.

The labeled case is A326213.
The undirected case is A283420 (without loops).
Unlabeled digraphs containing a Hamiltonian path are A326221.
Unlabeled digraphs not containing a Hamiltonian cycle are A326223.
Cf. A000595, A002416, A003087, A003216, A057864.

A000595(n) = a(n) + A326221(n).

A326205 Number of n-vertex labeled simple graphs not containing a Hamiltonian path.

Original entry on oeis.org

1, 1, 1, 4, 30, 391, 9400, 398140, 30500696, 4161339596, 1058339281896, 515295969951016

Offset: 0

Gus Wiseman, Jun 14 2019

A path is Hamiltonian if it passes through every vertex exactly once.

Wikipedia, Hamiltonian path
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.
Gus Wiseman, The a(4) = 30 simple graphs not containing a Hamiltonian path.

The unlabeled case is A283420.
The case for digraphs is A326213 (without loops) or A326216 (with loops).
Simple graphs with a Hamiltonian path are A326206.
Simple graphs without a Hamiltonian cycle are A326207.
Cf. A003216, A006125, A057864.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],FindHamiltonianPath[Graph[Range[n],#]]=={}&]],{n,0,4}] (* Mathematica 10.2+ *)

A006125(n) = a(n) + A326206(n).

a(7)-a(11) added from formula by Falk Hüffner, Jun 21 2019

A326223 Number of non-Hamiltonian unlabeled n-vertex digraphs (with loops).

Original entry on oeis.org

1, 0, 7, 80, 2186

Offset: 0

Gus Wiseman, Jun 15 2019

A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.

			Non-isomorphic representatives of the a(2) = 7 digraph edge-sets:
  {}
  {11}
  {12}
  {11,12}
  {11,21}
  {11,22}
  {11,12,22}

Gus Wiseman, Non-isomorphic representatives of the a(3) = 80 non-Hamiltonian digraphs.

The labeled case is A326220.
The case without loops is A326222.
The undirected case is A246446 (without loops) or A326239 (with loops).
Hamiltonian unlabeled digraphs are A326226.
Unlabeled digraphs not containing a Hamiltonian path are A326224.
Cf. A000595, A002416, A003087, A003216, A283420, A326204, A326218, A326225.

A326213 Number of labeled n-vertex digraphs (with loops) not containing a (directed) Hamiltonian path.

Original entry on oeis.org

1, 2, 4, 128, 12352, 3826272, 3775441536

Offset: 0

Gus Wiseman, Jun 15 2019

A path is Hamiltonian if it passes through every vertex exactly once.

Wikipedia, Hamiltonian path
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

The unlabeled case is A326224.
The case without loops is A326216.
Digraphs containing a Hamiltonian path are A326214.
Digraphs not containing a Hamiltonian cycle are A326220.
Cf. A000595, A002416, A003024, A003216, A057864, A283420, A326204, A326206, A326221.

Table[Length[Select[Subsets[Tuples[Range[n],2]],FindHamiltonianPath[Graph[Range[n],DirectedEdge@@@#]]=={}&]],{n,0,3}] (* Mathematica 10.2+ *)

A002416(n) = a(n) + A326214(n).

a(5)-a(6) from Bert Dobbelaere, Jun 11 2024

cp's OEIS Frontend

A003216 Number of Hamiltonian graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A057864 Number of simple traceable graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A246446 Number of nonhamiltonian graphs with n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326206 Number of n-vertex labeled simple graphs containing a Hamiltonian path.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326208 Number of Hamiltonian labeled simple graphs with n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326221 Number of unlabeled n-vertex digraphs (with loops) containing a Hamiltonian path.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A326224 Number of unlabeled n-vertex digraphs (with loops) not containing a Hamiltonian path.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A326205 Number of n-vertex labeled simple graphs not containing a Hamiltonian path.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326223 Number of non-Hamiltonian unlabeled n-vertex digraphs (with loops).