cp's OEIS Frontend

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

%I A326220 #13 Jun 11 2024 15:38:01
%S A326220 1,0,12,392,46432,20023232,30595305216
%N A326220 Number of non-Hamiltonian labeled n-vertex digraphs (with loops).
%C A326220 A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.
%H A326220 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a>
%e A326220 The a(2) = 12 digraph edge-sets:
%e A326220   {}  {11}  {11,12}  {11,12,22}
%e A326220       {12}  {11,21}  {11,21,22}
%e A326220       {21}  {11,22}
%e A326220       {22}  {12,22}
%e A326220             {21,22}
%t A326220 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 A326220 The unlabeled case is A326223.
%Y A326220 The undirected case is A326239 (with loops) or A326207 (without loops).
%Y A326220 The case without loops is A326218.
%Y A326220 Digraphs (with loops) containing a Hamiltonian cycle are A326204.
%Y A326220 Digraphs (with loops) not containing a Hamiltonian path are A326213.
%Y A326220 Cf. A000595, A002416, A003024, A003216, A246446, A326208, A326219, A326222, A326224.
%K A326220 nonn,more
%O A326220 0,3
%A A326220 _Gus Wiseman_, Jun 15 2019
%E A326220 a(5)-a(6) from _Bert Dobbelaere_, Jun 11 2024