cp's OEIS Frontend

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

%I A326218 #8 Jun 16 2019 22:33:50
%S A326218 1,0,3,49,2902
%N A326218 Number of non-Hamiltonian labeled n-vertex digraphs (without loops).
%C A326218 A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.
%H A326218 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a>
%F A326218 A053763(n) = a(n) + A326219(n).
%e A326218 The a(3) = 49 edge-sets:
%e A326218   {}  {12}  {12,13}  {12,13,21}  {12,13,21,23}
%e A326218       {13}  {12,21}  {12,13,23}  {12,13,21,31}
%e A326218       {21}  {12,23}  {12,13,31}  {12,13,23,32}
%e A326218       {23}  {12,31}  {12,13,32}  {12,13,31,32}
%e A326218       {31}  {12,32}  {12,21,23}  {12,21,23,32}
%e A326218       {32}  {13,21}  {12,21,31}  {12,21,31,32}
%e A326218             {13,23}  {12,21,32}  {13,21,23,31}
%e A326218             {13,31}  {12,23,32}  {13,23,31,32}
%e A326218             {13,32}  {12,31,32}  {21,23,31,32}
%e A326218             {21,23}  {13,21,23}
%e A326218             {21,31}  {13,21,31}
%e A326218             {21,32}  {13,23,31}
%e A326218             {23,31}  {13,23,32}
%e A326218             {23,32}  {13,31,32}
%e A326218             {31,32}  {21,23,31}
%e A326218                      {21,23,32}
%e A326218                      {21,31,32}
%e A326218                      {23,31,32}
%t A326218 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 *)
%Y A326218 The unlabeled case is A326222.
%Y A326218 The undirected case is A326207.
%Y A326218 The case with loops is A326220.
%Y A326218 Digraphs (without loops) containing a Hamiltonian cycle are A326219.
%Y A326218 Digraphs (without loops) not containing a Hamiltonian path are A326216.
%Y A326218 Cf. A000595, A002416, A003024, A003216, A246446, A326204, A326213, A326223, A326225.
%K A326218 nonn,more
%O A326218 0,3
%A A326218 _Gus Wiseman_, Jun 15 2019