A326225 -id:A326225

A003216

Number of Hamiltonian graphs with n nodes.
(Formerly M2764)

+10
50

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

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

Table of n, a(n) for n=1..13.

John Asplund, N. Bradley Fox, and Arran Hamm, New Perspectives on Neighborhood-Prime Labelings of Graphs, arXiv:1804.02473 [math.CO], 2018.

J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)

Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, preprint, 2015.

Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, arXiv:1505.06508 [math.CO], 2015.

Jan Goedgebeur, Barbara Meersman, and Carol T. Zamfirescu, Graphs with few Hamiltonian Cycles, arXiv:1812.05650 [math.CO], 2018-2019.

Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Eric Weisstein's World of Mathematics, Hamiltonian Cycle

Eric Weisstein's World of Mathematics, Hamiltonian Graph

Wikipedia, Hamiltonian path

Gus Wiseman, Non-isomorphic representatives of the a(5) = 8 simple graphs containing a Hamiltonian cycle.

FORMULA

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

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.

KEYWORD

nonn,nice,hard,more

AUTHOR

N. J. A. Sloane

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

STATUS

approved

A326226

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

+10
10

0, 2, 3, 24, 858

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

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

LINKS

Table of n, a(n) for n=0..4.

Wikipedia, Hamiltonian path

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

EXAMPLE

Non-isomorphic representatives of the a(2) = 3 digraph edge-sets:

{12,21}

{11,12,21}

{11,12,21,22}

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

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.

KEYWORD

nonn,hard,more

AUTHOR

Gus Wiseman, Jun 14 2019

STATUS

approved

A326223

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

+10
8

1, 0, 7, 80, 2186

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

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

LINKS

Table of n, a(n) for n=0..4.

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

EXAMPLE

Non-isomorphic representatives of the a(2) = 7 digraph edge-sets:

{}

{11}

{12}

{11,12}

{11,21}

{11,22}

{11,12,22}

CROSSREFS

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.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 15 2019

STATUS

approved

A326217

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

+10
7

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

Table of n, a(n) for n=0..7.

Wikipedia, Hamiltonian path

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

FORMULA

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

EXAMPLE

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}

MATHEMATICA

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

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.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 15 2019

EXTENSIONS

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

STATUS

approved

A326218

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

+10
7

1, 0, 3, 49, 2902

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

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

LINKS

Table of n, a(n) for n=0..4.

Wikipedia, Hamiltonian path

FORMULA

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

EXAMPLE

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}

MATHEMATICA

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

CROSSREFS

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.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 15 2019

STATUS

approved

A326219

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

+10
7

0, 1, 1, 15, 1194

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

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

LINKS

Table of n, a(n) for n=0..4.

Wikipedia, Hamiltonian path

FORMULA

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

EXAMPLE

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}

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

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.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 15 2019

STATUS

approved

A326214

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

+10
6

0, 0, 12, 384, 53184

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

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

LINKS

Table of n, a(n) for n=0..4.

Wikipedia, Hamiltonian path

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

FORMULA

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

EXAMPLE

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}

MATHEMATICA

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

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.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 15 2019

STATUS

approved

A326216

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

+10
6

1, 1, 1, 16, 772

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

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

LINKS

Table of n, a(n) for n=0..4.

Wikipedia, Hamiltonian path

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

FORMULA

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

EXAMPLE

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}

MATHEMATICA

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

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.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 15 2019

STATUS

approved

A326222

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

+10
6

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

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

LINKS

Table of n, a(n) for n=0..7.

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

FORMULA

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

CROSSREFS

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.

KEYWORD

nonn,hard,more

AUTHOR

Gus Wiseman, Jun 15 2019

EXTENSIONS

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

STATUS

approved

A326215

Number of Hamiltonian unlabeled n-vertex graphs with loops.

+10
4

0, 2, 0, 4, 20

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

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

LINKS

Table of n, a(n) for n=0..4.

Wikipedia, Hamiltonian path

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

EXAMPLE

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}

CROSSREFS

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.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 17 2019

STATUS

approved