Two eulerian trails of $K_{2n+1}$ are defined to be equivalent if the orientations obtained by orienting the edges as traversed by the trails are isomorphic as digraph. How many non-equivalent trails are there?

  • $\begingroup$ The eulerian trails $0\to 1\to 2\to 0$ and $0\to 2\to 1\to 0$ of the complete graph $K_3$ are considered non-equivalent? $\endgroup$ – Freddy Barrera Apr 22 at 12:28
  • 2
    $\begingroup$ @FreddyBarrera Those would be considered equivalent since they are isomorphic as digraphs (both are just directed triangles). $\endgroup$ – Tony Huynh Apr 22 at 13:14
  • $\begingroup$ @FreddyBarrera, yes they are the same. Number for $K_3$ is 1. $\endgroup$ – hbm Apr 22 at 13:49

If I understand your question, you are asking for the number of isomorphism classes of regular tournaments.

There are no exact formulas. See http://oeis.org/A096368 for counts up to 15 vertices.

The asymptotic number is known. It is $RT(2n+1)/(2n+1)!$, where $RT(2n+1)$ is given in the abstract of this paper.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.