The On-Line Encyclopedia of Integer Sequences (OEIS)

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A326216 revision #13

A326216

Number of labeled n-vertex digraphs (without loops) not containing a (directed) Hamiltonian path.

1, 1, 1, 16, 772

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

OFFSET

0,4

COMMENTS

A path is Hamiltonian if it passes through every vertex exactly once.

LINKS

Table of n, a(n) for n=0..4.

Wikipedia, Hamiltonian path

Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

FORMULA

A053763(n) = a(n) + A326217(n).

EXAMPLE

The a(3) = 16 edge-sets:

{} {12} {12,13}

{13} {12,21}

{21} {12,32}

{23} {13,23}

{31} {13,31}

{32} {21,23}

{21,31}

{23,32}

{31,32}

MATHEMATICA

Table[Length[Select[Subsets[Select[Tuples[Range[n], 2], UnsameQ@@#&]], FindHamiltonianPath[Graph[Range[n], DirectedEdge@@@#]]=={}&]], {n, 4}] (* Mathematica 10.2+ *)

CROSSREFS

Unlabeled digraphs not containing a Hamiltonian path are A326224.

The undirected case is A326205.

The unlabeled undirected case is A283420.

The case with loops is A326213.

Digraphs (without loops) containing a Hamiltonian path are A326217.

Digraphs (without loops) not containing a Hamiltonian cycle are A326218.

Cf. A000595, A002416, A003024, A003216, A057864, A326206, A326214, A326220, A326221, A326225.

Sequence in context: A134183 A042109 A221061 * A194610 A215171 A224736

Adjacent sequences: A326213 A326214 A326215 * A326217 A326218 A326219

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 15 2019

STATUS

editing