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

1, 0, 12, 392, 46432, 20023232, 30595305216

Offset: 0

Author

Gus Wiseman, Jun 15 2019

Keywords

• nonn
• more

Comments

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

Examples

			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}
		

Links

• Wikipedia, Hamiltonian path

Crossrefs

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.

Programs

Mathematica

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

Extensions

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