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

A283420 Number of simple (not necessarily connected) untraceable graphs on n nodes.

Original entry on oeis.org

0, 1, 2, 6, 16, 65, 310, 2316, 26241, 522596, 18766354

Offset: 1

Eric W. Weisstein, May 14 2017

Eric Weisstein's World of Mathematics, Untraceable 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, The a(5) = 16 unlabeled simple graphs not containing a Hamiltonian path.

Cf. A000088 (number of simple graphs on n vertices).
Cf. A057864 (number of simple traceable graphs on n vertices).
Cf. A283421 (number of simple connected untraceable graphs on n vertices).
The labeled case is A326205.
The directed case is A326224 (with loops).
Unlabeled simple graphs not containing a Hamiltonian cycle are A246446.
Cf. A003216, A326206, A326217, A326221.

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

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

A326204 Number of Hamiltonian labeled n-vertex digraphs (with loops).

Original entry on oeis.org

0, 2, 4, 120, 19104

Offset: 0

Gus Wiseman, Jun 14 2019

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

			The a(2) = 4 digraph edge-sets:
  {12,21}
  {11,12,21}
  {12,21,22}
  {11,12,21,22}

Wikipedia, Hamiltonian path

The unlabeled case is A326226.
The case without loops is A326219.
The undirected case (without loops) is A326208.
Non-Hamiltonian digraphs are A326220.
Digraphs containing a Hamiltonian path are A326214.
Cf. A000595, A002416, A003024, A003216, A057864.

Table[Length[Select[Subsets[Tuples[Range[n],2]],FindHamiltonianCycle[Graph[Range[n],DirectedEdge@@@#]]!={}&]],{n,0,4}] (* Mathematica 8.0+. Warning: Using HamiltonianGraphQ instead of FindHamiltonianCycle returns a(4) = 19200 which is incorrect *)

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

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

Original entry on oeis.org

0, 2, 3, 24, 858

Offset: 0

Gus Wiseman, Jun 14 2019

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

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

Wikipedia, Hamiltonian path
Gus Wiseman, Non-isomorphic representatives of the a(3) = 24 Hamiltonian digraphs

The labeled case is A326204.
The case without loops is A326225.
The undirected case is A003216 (without loops) or A326215 (with loops).
Unlabeled non-Hamiltonian digraphs are A326223.
Unlabeled digraphs with a Hamiltonian path are A326221.
Cf. A000595, A002416, A003087, A057864, A246446, A326208.

dinorm[m_]:=If[m=={},{},If[Union@@m!=Range[Max@@Flatten[m]],dinorm[m/. Apply[Rule,Table[{(Union@@m)[[i]],i},{i,Length[Union@@m]}],{1}]],First[Sort[dinorm[m,1]]]]];
dinorm[m_,aft_]:=If[Length[Union@@m]<=aft,{m},With[{mx=Table[Count[m,i,{2}],{i,Select[Union@@m,#1>=aft&]}]},Union@@(dinorm[#1,aft+1]&)/@Union[Table[Map[Sort,m/. {par+aft-1->aft,aft->par+aft-1},{0}],{par,First/@Position[mx,Max[mx]]}]]]];
Table[Length[Select[Union[dinorm/@Subsets[Tuples[Range[n],2]]],FindHamiltonianCycle[Graph[Range[n],DirectedEdge@@@#]]!={}&]],{n,0,4}] (* Mathematica 8.0+. Warning: Using HamiltonianGraphQ instead of FindHamiltonianCycle returns a(4) = 867 which is incorrect *)

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

cp's OEIS Frontend

A003216 Number of Hamiltonian graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A283420 Number of simple (not necessarily connected) untraceable graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

A246446 Number of nonhamiltonian graphs with n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326204 Number of Hamiltonian labeled n-vertex digraphs (with loops).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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