A003216 -id:A003216 - cp's OEIS frontend

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

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

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

Gus Wiseman, Jun 15 2019

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

			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}

Wikipedia, Hamiltonian path

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.

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

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

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

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

Gus Wiseman, Jun 15 2019

			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}

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

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.

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

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

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

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

Original entry on oeis.org

1, 0, 3, 49, 2902

Offset: 0

Gus Wiseman, Jun 15 2019

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

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

Wikipedia, Hamiltonian path

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

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

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

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

Original entry on oeis.org

0, 1, 1, 15, 1194

Offset: 0

Gus Wiseman, Jun 15 2019

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

			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}

Wikipedia, Hamiltonian path

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.

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

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

A367123 Number of Hamiltonian cycles in the n-omino graph defined in A098891.

Original entry on oeis.org

1, 1, 0, 2, 16800

Offset: 1

Pontus von Brömssen, Nov 05 2023

The n-omino graph has all A000105(n) free n-ominoes as nodes, and two n-ominoes are joined by an edge if one can be obtained from the other by moving one cell. The intermediate is allowed not to be a connected (n-1)-omino; for example, there is an edge between the V and W pentominoes, but to transform one to the other the central cell must be moved, and the remaining 4 cells is not a tetromino.
A cycle and its reverse are not both counted.
We follow the convention in A003216 that the complete graphs on 1 and 2 nodes have 1 and 0 Hamiltonian cycles, respectively, so that a(1) = a(2) = 1 and a(3) = 0, but it could also be argued that a(1) = a(2) = 0 and/or a(3) = 1.

			For n = 4, there are a(4) = 2 Hamiltonian cycles in the tetromino graph: I-L-O-S-T-I and I-L-S-O-T-I, using conventional names of the tetrominoes.
For n = 5, one of the a(5) = 16800 Hamiltonian cycles in the pentomino graph is I-L-P-U-V-T-N-W-Z-F-X-Y-I.
See links for an example for n = 6.

Pontus von Brömssen, A Hamiltonian cycle in the hexomino graph. In this cycle, all intermediates are (connected) pentominoes.
Index entries for sequences related to polyominoes.

Cf. A000105, A003216, A098891, A367124, A367125, A367126, A367127, A367436.

a(n) > 0 for 4 <= n <= 13.

a(n) >= A367436(n).

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula