A057864 -id:A057864 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

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

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

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}]

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.

A309524 Triangle read by rows: T(n,k) is the number of simple connected graphs on n nodes with longest path having k nodes, (1 <= k <= n).

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 0, 0, 1, 5, 0, 0, 1, 2, 18, 0, 0, 1, 3, 17, 91, 0, 0, 1, 3, 29, 86, 734, 0, 0, 1, 4, 42, 176, 864, 10030, 0, 0, 1, 4, 64, 309, 2032, 10243, 248427

Offset: 1

Andrew Howroyd, Sep 06 2019

Paths here are subgraphs that are isomorphic to a path graph and are measured by the number of vertices they contain rather than the number of edges. No vertex can appear more than once.

Paths with three vertices exist in all connected graphs with at least three vertices. For n > 3, the star graph is the only graph in which longer paths are not possible.

			Triangle begins:
  1;
  0, 1;
  0, 0, 2;
  0, 0, 1, 5;
  0, 0, 1, 2, 18;
  0, 0, 1, 3, 17,  91;
  0, 0, 1, 3, 29,  86,  734;
  0, 0, 1, 4, 42, 176,  864, 10030;
  0, 0, 1, 4, 64, 309, 2032, 10243, 248427;
  ...

Eric Weisstein's World of Mathematics, Longest Path
Eric Weisstein's World of Mathematics, Traceable Graph

Row sums are A001349.
Right diagonal is A057864.
Cf. A325455 (circumference = longest cycle).
Cf. A307457.

A283421 Number of connected untraceable graphs on n vertices.

Original entry on oeis.org

0, 0, 0, 1, 3, 21, 119, 1087, 12653, 233999, 6469055

Offset: 1

Eric W. Weisstein, May 14 2017

Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Untraceable Graph

Cf. A000088 (number of simple graphs on n vertices).
Cf. A001349 (number of simple connected graphs on n vertices).
Cf. A057864 (number of traceable simple graphs on n vertices).
Cf. A283420 (number of simple untraceable not necessarily connected graphs on n vertices).

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

cp's OEIS Frontend

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

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

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

Views

Author

Keywords

Comments