cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-9 of 9 results.

A003216 Number of Hamiltonian graphs with n nodes.

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

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

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

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

Original entry on oeis.org

0, 2, 4, 120, 19104
Offset: 0

Views

Author

Gus Wiseman, Jun 14 2019

Keywords

Comments

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

Examples

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

Links

Crossrefs

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.

Programs

  • Mathematica
    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

Views

Author

Gus Wiseman, Jun 14 2019

Keywords

Comments

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

Links

Crossrefs

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.

Programs

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

Formula

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

Extensions

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

Views

Author

Gus Wiseman, Jun 14 2019

Keywords

Comments

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

Examples

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

Links

Crossrefs

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.

Programs

  • Mathematica
    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 *)

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

Original entry on oeis.org

1, 0, 12, 392, 46432, 20023232, 30595305216
Offset: 0

Views

Author

Gus Wiseman, Jun 15 2019

Keywords

Comments

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

Examples

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

Links

Crossrefs

The unlabeled case is A326223.
The undirected case is A326239 (with loops) or A326207 (without loops).
The case without loops is A326218.
Digraphs (with loops) containing a Hamiltonian cycle are A326204.
Digraphs (with loops) not containing a Hamiltonian path are A326213.
Cf. A000595, A002416, A003024, A003216, A246446, A326208, A326219, A326222, A326224.

Programs

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

Extensions

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

A326217 Number of labeled n-vertex digraphs (without loops) containing a Hamiltonian path.

Original entry on oeis.org

0, 0, 3, 48, 3324, 929005, 1014750550, 4305572108670
Offset: 0

Views

Author

Gus Wiseman, Jun 15 2019

Keywords

Examples

			The a(3) = 48 edge-sets:
  {12,23}  {12,13,21}  {12,13,21,23}  {12,13,21,23,31}  {12,13,21,23,31,32}
  {12,31}  {12,13,23}  {12,13,21,31}  {12,13,21,23,32}
  {13,21}  {12,13,31}  {12,13,21,32}  {12,13,21,31,32}
  {13,32}  {12,13,32}  {12,13,23,31}  {12,13,23,31,32}
  {21,32}  {12,21,23}  {12,13,23,32}  {12,21,23,31,32}
  {23,31}  {12,21,31}  {12,13,31,32}  {13,21,23,31,32}
           {12,21,32}  {12,21,23,31}
           {12,23,31}  {12,21,23,32}
           {12,23,32}  {12,21,31,32}
           {12,31,32}  {12,23,31,32}
           {13,21,23}  {13,21,23,31}
           {13,21,31}  {13,21,23,32}
           {13,21,32}  {13,21,31,32}
           {13,23,31}  {13,23,31,32}
           {13,23,32}  {21,23,31,32}
           {13,31,32}
           {21,23,31}
           {21,23,32}
           {21,31,32}
           {23,31,32}

Links

Crossrefs

The undirected case is A326206.
The unlabeled undirected case is A057864.
The case with loops is A326214.
Unlabeled digraphs with a Hamiltonian path are A326221.
Digraphs (without loops) not containing a Hamiltonian path are A326216.
Digraphs (without loops) containing a Hamiltonian cycle are A326219.
Cf. A000595, A002416, A003024, A003216, A283420, A326204, A326208, A326213, A326225.

Programs

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

Formula

A053763(n) = a(n) + A326216(n).

Extensions

a(5)-a(7) from Bert Dobbelaere, Feb 21 2023

A326219 Number of labeled n-vertex Hamiltonian digraphs (without loops).

Original entry on oeis.org

0, 1, 1, 15, 1194
Offset: 0

Views

Author

Gus Wiseman, Jun 15 2019

Keywords

Comments

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

Examples

			The a(3) = 15 edge-sets:
  {12,23,31}  {12,13,21,32}  {12,13,21,23,31}  {12,13,21,23,31,32}
  {13,21,32}  {12,13,23,31}  {12,13,21,23,32}
              {12,21,23,31}  {12,13,21,31,32}
              {12,23,31,32}  {12,13,23,31,32}
              {13,21,23,32}  {12,21,23,31,32}
              {13,21,31,32}  {13,21,23,31,32}

Links

Crossrefs

The unlabeled case is A326225.
The undirected case is A326208 (without loops) or A326240 (with loops).
The case with loops is A326204.
Digraphs (without loops) not containing a Hamiltonian cycle are A326218.
Digraphs (without loops) containing a Hamiltonian path are A326217.
Cf. A000595, A002416, A003024, A003216, A053763, A246446, A326220, A326226.

Programs

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

Formula

A053763(n) = a(n) + A326218(n).

A326207 Number of non-Hamiltonian labeled simple graphs with n vertices.

Original entry on oeis.org

1, 0, 2, 7, 54, 806, 22690, 1200396, 116759344, 20965139168, 6954959632776, 4363203307789888
Offset: 0

Views

Author

Gus Wiseman, Jun 15 2019

Keywords

Comments

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

Examples

			The a(3) = 7 edge sets:
  {}
  {12}
  {13}
  {23}
  {12,13}
  {12,23}
  {13,23}

Links

Crossrefs

The unlabeled version is A246446.
The directed version is A326220 (with loops) or A326216 (without loops).
Simple graphs with a Hamiltonian cycle are A326208.
Simple graphs without a Hamiltonian path are A326205.
Cf. A003216, A006125, A057864, A283420.

Programs

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

Formula

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

Extensions

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

A326240 Number of Hamiltonian labeled n-vertex graphs with loops.

Original entry on oeis.org

0, 2, 0, 8, 160, 6976, 644992
Offset: 0

Views

Author

Gus Wiseman, Jun 17 2019

Keywords

Comments

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

Examples

			The a(3) = 8 edge-sets:
  {12,13,23}  {11,12,13,23}  {11,12,13,22,23}  {11,12,13,22,23,33}
              {12,13,22,23}  {11,12,13,23,33}
              {12,13,23,33}  {12,13,22,23,33}

Crossrefs

The unlabeled case is A326215.
The directed case is A326204 (with loops) or A326219 (without loops).
The case without loops A326208.
Graphs with loops not containing a Hamiltonian cycle are A326239.
Cf. A000088, A003216, A006125, A057864, A283420.

Programs

  • Mathematica
    Table[Length[Select[Subsets[Select[Tuples[Range[n],2],OrderedQ]],FindHamiltonianCycle[Graph[Range[n],#]]!={}&]],{n,0,5}]

Formula

a(n) = A326208(n) * 2^n.
Showing 1-9 of 9 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.