Digraphs with exactly one Eulerian tour

Abstract

We give two combinatorial proofs of the fact that the number of loopless digraphs on the vertex set $[n]$ with no isolated vertices and with exactly one Eulerian tour up to a cyclic shift is $\frac{1}{2}(n-1)!C_n$, where $C_n$ denotes the $n$-th Catalan number. We construct a bijection with a set of labeled rooted plane trees and with a set of valid parenthesis arrangements.

8 pages, 7 figures