A003216 -id:A003216 - cp's OEIS frontend

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

0, 0, 12, 384, 53184

Offset: 0

Gus Wiseman, Jun 15 2019

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

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

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 A326221.
The undirected case is A326206.
The case without loops is A326217.
Digraphs not containing a Hamiltonian path are A326213.
Digraphs containing a Hamiltonian cycle are A326204.
Cf. A000595, A002416, A003024, A003216, A057864, A326224, A326225, A326226.

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

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

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

Original entry on oeis.org

1, 1, 1, 16, 772

Offset: 0

Gus Wiseman, Jun 15 2019

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

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

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

Unlabeled digraphs not containing a Hamiltonian path are A326224.
The undirected case is A326205.
The unlabeled undirected case is A283420.
The case with loops is A326213.
Digraphs (without loops) containing a Hamiltonian path are A326217.
Digraphs (without loops) not containing a Hamiltonian cycle are A326218.
Cf. A000595, A002416, A003024, A003216, A057864, A326206, A326214, A326220, A326221, 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) + A326217(n).

A326222 Number of non-Hamiltonian unlabeled n-vertex digraphs (without loops).

Original entry on oeis.org

1, 0, 2, 12, 157, 5883, 696803, 255954536

Offset: 0

Gus Wiseman, Jun 15 2019

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

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

The labeled case is A326218 (without loops) or A326220 (with loops).
The undirected case (without loops) is A246446.
The case with loops is A326223.
Hamiltonian unlabeled digraphs are A326225 (without loops) or A003216 (with loops).
Cf. A000273, A000595, A002416, A003087, A053763, A326216, A326217, A326224, A326226.

a(n) = A000273(n) - A326225(n). - Pontus von Brömssen, Mar 17 2024

a(5)-a(7) (using A000273 and A326225) from Pontus von Brömssen, Mar 17 2024

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

Gus Wiseman, Jun 15 2019

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

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

Wikipedia, Hamiltonian path

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.

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

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

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

A126149 Number of connected nonhamiltonian graphs with n nodes.

Original entry on oeis.org

0, 1, 1, 3, 13, 64, 470, 4921, 83997, 2411453, 123544541, 11537642646, 2013389528672

Offset: 1

Jonathan Vos Post, Mar 07 2007

			a(10) = A001349(10) - A003216(10) = number of connected graphs on 10 unlabeled nodes - number of Hamiltonian graphs with 10 nodes = 11716571 - 9305118 = 2411453.
a(11) = A001349(11) - A003216(11) = number of connected graphs on 11 unlabeled nodes - number of Hamiltonian graphs with 11 nodes = 1006700565 - 883156024 = 123544541.

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.

Jan Goedgebeur, Barbara Meersman, Carol T. Zamfirescu, Graphs with few Hamiltonian Cycles, arXiv:1812.05650 [math.CO], 2018-2019.
Eric Weisstein's World of Mathematics, Nonhamiltonian Graph.

Cf. A000088, A001349, A003216, A022564.

Cf. A246446 (number of not-necessarily-connected simple nonhamiltonian graphs on n nodes).

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

Terms a(1)-a(9) corrected by Travis Hoppe, Jun 01 2014
a(11) added by Eric W. Weisstein, Aug 26 2014
a(12) from formula by Falk Hüffner, Aug 13 2017
a(13) added by Jan Goedgebeur, May 07 2019

A325455 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes with circumference k, (n >= 3, k >= 3).

Original entry on oeis.org

1, 1, 3, 4, 6, 8, 10, 24, 24, 48, 30, 87, 116, 226, 383, 83, 342, 527, 1283, 2663, 6196, 257, 1324, 2644, 6644, 17613, 55468, 177083

Offset: 3

Andrew Howroyd, Sep 06 2019

Trees are excluded since they do not have any cycle.

			Triangle begins:
    1;
    1,    3;
    4,    6,    8;
   10,   24,   24,   48;
   30,   87,  116,  226,   383;
   83,  342,  527, 1283,  2663,  6196;
  257, 1324, 2644, 6644, 17613, 55468, 177083;
  ...

Eric Weisstein's World of Mathematics, Graph Circumference
Eric Weisstein's World of Mathematics, Hamiltonian Graph

Right diagonal is A003216.
Row sums are A241841.
Cf. A128042, A309524, A325447.

A326215 Number of Hamiltonian unlabeled n-vertex graphs with loops.

Original entry on oeis.org

0, 2, 0, 4, 20

Offset: 0

Gus Wiseman, Jun 17 2019

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

			Non-isomorphic representatives of the a(3) = 4 edge-sets:
  {12,13,23}
  {12,13,23,33}
  {12,13,22,23,33}
  {11,12,13,22,23,33}

Wikipedia, Hamiltonian path
Gus Wiseman, Non-isomorphic representatives of the a(4) = 20 Hamiltonian graphs with loops.

The labeled case is A326240.
The directed case is A326226 (with loops) or A326225 (without loops).
The case without loops A003216.
Cf. A000088, A006125, A057864, A283420, A326239.

A326239 Number of non-Hamiltonian labeled n-vertex graphs with loops.

Original entry on oeis.org

1, 0, 8, 56, 864, 25792

Offset: 0

Gus Wiseman, Jun 16 2019

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

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

Wikipedia, Hamiltonian path

The directed case is A326204 (with loops) or A326218 (without loops).
Simple graphs containing a Hamiltonian cycle are A326240.
Simple graphs not containing a Hamiltonian path are A326205.
Cf. A000088, A003216, A006125, A057864, A283420.

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

A367436 Number of Hamiltonian cycles in the polyomino graph PG(n) defined in A367435.

Original entry on oeis.org

1, 1, 0, 2, 4080

Offset: 1

Pontus von Brömssen, Nov 18 2023

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.

Pontus von Brömssen, A Hamiltonian cycle in the heptomino graph.
Pontus von Brömssen, A Hamiltonian cycle in the hexomino graph.
MathOverflow, Generating all pentominoes by cutting and pasting.
Index entries for sequences related to polyominoes.

Cf. A003216, A367123, A367435.

a(n) <= A367123(n).

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

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

Original entry on oeis.org

0, 2, 0, 8, 160, 6976, 644992

Offset: 0

Gus Wiseman, Jun 17 2019

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

			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}

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.

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

a(n) = A326208(n) * 2^n.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A326222 Number of non-Hamiltonian unlabeled n-vertex digraphs (without loops).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A126149 Number of connected nonhamiltonian graphs with n nodes.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions

A325455 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes with circumference k, (n >= 3, k >= 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A326215 Number of Hamiltonian unlabeled n-vertex graphs with loops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A326239 Number of non-Hamiltonian labeled n-vertex graphs with loops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica