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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A326216 Number of labeled n-vertex digraphs (without loops) not containing a (directed) Hamiltonian path. 6
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.

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

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 19 23:47 EST 2022. Contains 350467 sequences. (Running on oeis4.)