A326218 - OEIS

A326218

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

1, 0, 3, 49, 2902

(list; graph; refs; listen; history; text; internal format)

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