login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A326220 Number of non-Hamiltonian labeled n-vertex digraphs (with loops). 8
1, 0, 12, 392, 46432 (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

EXAMPLE

The a(2) = 12 digraph edge-sets:

  {}  {11}  {11,12}  {11,12,22}

      {12}  {11,21}  {11,21,22}

      {21}  {11,22}

      {22}  {12,22}

            {21,22}

MATHEMATICA

Table[Length[Select[Subsets[Tuples[Range[n], 2]], FindHamiltonianCycle[Graph[Range[n], DirectedEdge@@@#]]=={}&]], {n, 4}] (* Mathematica 8.0+. Warning: Using HamiltonianGraphQ instead of FindHamiltonianCycle returns a(4) = 46336 which is incorrect *)

CROSSREFS

The unlabeled case is A326223.

The undirected case is A326239 (with loops) or A326207 (without loops).

The case without loops is A326218.

Digraphs (with loops) containing a Hamiltonian cycle are A326204.

Digraphs (with loops) not containing a Hamiltonian path are A326213.

Cf. A000595, A002416, A003024, A003216, A246446, A326208, A326219, A326222, A326224.

Sequence in context: A326214 A187513 A138914 * A308129 A286038 A276482

Adjacent sequences:  A326217 A326218 A326219 * A326221 A326222 A326223

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 October 26 11:59 EDT 2021. Contains 348267 sequences. (Running on oeis4.)