A326220 - OEIS

%I #13 Jun 11 2024 15:38:01

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

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

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

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a>

%e The a(2) = 12 digraph edge-sets:

%e   {}  {11}  {11,12}  {11,12,22}

%e       {12}  {11,21}  {11,21,22}

%e       {21}  {11,22}

%e       {22}  {12,22}

%e             {21,22}

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

%Y The unlabeled case is A326223.

%Y The undirected case is A326239 (with loops) or A326207 (without loops).

%Y The case without loops is A326218.

%Y Digraphs (with loops) containing a Hamiltonian cycle are A326204.

%Y Digraphs (with loops) not containing a Hamiltonian path are A326213.

%Y Cf. A000595, A002416, A003024, A003216, A246446, A326208, A326219, A326222, A326224.

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Jun 15 2019

%E a(5)-a(6) from _Bert Dobbelaere_, Jun 11 2024