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

1, 0, 3, 49, 2902

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.

Sequence in context: A012100 A106842 A298697 * A203743 A086459 A180602

Adjacent sequences: A326215 A326216 A326217 * A326219 A326220 A326221

Keyword

nonn,more

Author

Gus Wiseman, Jun 15 2019

Status

approved