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.

A057864 Number of simple traceable graphs on n nodes.

Original entry on oeis.org

1, 1, 2, 5, 18, 91, 734, 10030, 248427, 11482572, 1000231510
Offset: 1

Views

Author

Eric W. Weisstein

Keywords

Comments

Number of undirected graphs on n nodes possessing a Hamiltonian path (not circuit).

Links

Crossrefs

Main diagonal of A309524.
The labeled case is A326206.
The directed case is A326221 (with loops).
Unlabeled simple graphs not containing a Hamiltonian path are A283420.
Unlabeled simple graphs containing a Hamiltonian cycle are A003216.
Cf. A000088, A006125, A246446, A283420, A326205, A326217.

Formula

A000088(n) = a(n) + A283420(n). - Gus Wiseman, Jun 17 2019

Extensions

a(8) and a(9) from Eric W. Weisstein, Jun 04 2004
a(10) from Eric W. Weisstein, May 27 2009
a(11) added using tinygraph by Falk Hüffner, Jan 19 2016

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

Views

Author

Eric W. Weisstein, May 14 2017

Keywords

Links

Crossrefs

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.

Formula

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

Views

Author

Eric W. Weisstein, Aug 26 2014

Keywords

Links

Crossrefs

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.

Programs

Formula

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

Extensions

a(12) from formula by Falk Hüffner, Aug 13 2017
a(13) added by Jan Goedgebeur, May 07 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

Views

Author

Gus Wiseman, Jun 15 2019

Keywords

Comments

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

Links

Crossrefs

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.

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) + A326207(n).

Extensions

a(7)-a(11) added using tinygraph by Falk Hüffner, Jun 21 2019

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

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

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) + A326206(n).

Extensions

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

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

Views

Author

Gus Wiseman, Jun 15 2019

Keywords

Comments

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

Links

Crossrefs

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.

Programs

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

Formula

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

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

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

Views

Author

Gus Wiseman, Jun 15 2019

Keywords

Comments

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

Examples

			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}

Links

Crossrefs

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.

Programs

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

Formula

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

Views

Author

Gus Wiseman, Jun 15 2019

Keywords

Comments

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

Examples

			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}

Links

Crossrefs

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.

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) + A326217(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.