Digraphs with exactly one Eulerian tour

Question

I’ve been thinking about the following problem from Richard Stanley’s list of bijective proof problems (2009). There, this problem is said to lack a combinatorial solution. The problem is the following:

An Eulerian tour in a directed graph $D$ is a permutation $e_1e_2 \cdots e_q$ of the edges of $D$ such that the final vertex (head) of $e_i$ is the initial vertex (tail) of $e_{i+1}$, $1 \leq i \leq q$, where the subscripts are taken modulo $q$. Thus any cyclic shift $e_ie_{i+1} \cdots e_qe_1 \cdots e_{i−1}$ of an Eulerian tour is also an Eulerian tour. For $n \geq 2$, the number of loopless (i.e., no edge from a vertex to itself) digraphs on the vertex set [n] with no isolated vertices and with exactly one Eulerian tour (up to cyclic shift) is given by $\frac{1}{2} (n − 1)! C_n = (2n-1)_{n-2}$.

I tried to find some approaches to it on the internet without much success. Some things I observed about such digraphs are that they must be connected, balanced, the outdegree of a vertex is either 1 or 2, and in the case that all vertices have outdegree 1 we obtain $(n-1)!$ digraphs (corresponding to all the possible ways to arrange the vertices in a cycle).

Since Richard Stanley’s list is from 2009, I wonder if anyone knows of a combinatorial solution to this problem or any papers that discuss it. It would also be helpful if someone knew the algebraic solution to this problem, or another property that such graphs follow. Maybe a solution can be achieved combining the BEST Theorem and the Matrix-Tree Theorem?

Answer 1

Graphs obtained from a (directed) cycle by a repeated operation of attaching a (directed) cycle to a vertex of degree $2$ have unique Eulerian tour.

The sequence appears in OEIS: http://oeis.org/A102693. It starts with "$2,5,42,\dots$" for $n=2,3,4\dots$. For $n=2,3,4,$ these numbers count exactly the digraphs constructed above.

Regarding enumeration, one possibility would be to count rooted graphs with the above property; there seems to be a bijection with labeled rooted plane trees (each directed cycle goes through a node and all its children from left to right).

Answer 2

Here is a combinatorial proof I found.

First, note that this is equivalent to allowing loops but demanding that all vertices have indegree and outdegree 2 (add a loop to each vertex of in/outdegree 1). This formulation will be more convenient.

Now we construct a bijection between the set of such digraphs with identified edge and the set of valid ways to arrange $n$ distinguishable pairs of open/close parentheses (of size $n!\cdot C_n$), showing that the number of such digraphs is $\frac{(n-1)!\cdot C_n}{2}$.

Edge-pointed digraphs $\to$ Parentheses arrangement

Suppose you have a valid digraph with identified edge $e$. Following the unique Eulerian circuit, starting at $e$, open the $i$'th parenthesis when you pass through vertex $i$ for the first time and close the $i$'th parenthesis when you pass through it for the second time. For example, the following digraph (with $2\to 1$ identified) yields the string $(_1)_1(_3)_3(_2)_2$:

To show that the resulting string of parentheses is valid, we have to show that we can't have something of the form $\cdots(_i\cdots (_j \cdots )_i\cdots )_j \cdots$. In other words, the circuit can't have the form $i \xrightarrow[]{a} j \xrightarrow[]{b} i \xrightarrow[]{c} j \xrightarrow[]{d} i$ for some walks $a,b,c,d$. This is clearly impossible because otherwise we would have a second eulerian circuit $i \xrightarrow[]{a} j \xrightarrow[]{d} i \xrightarrow[]{c} j \xrightarrow[]{b} i$, contradicting the uniqueness of the eulerian circuit.

Parentheses arrangement $\to$ Edge pointed digraphs

Given a valid parentheses arrangement $(_i \cdots )_j$, we obtain a digraph by putting an edge between the corresponding vertices of any pair of consecutive parentheses (from the first parenthesis to the second) and an edge from $j$ to $i$. Identify edge $j\to i$. For example, the parentheses arrangement $(_1(_2)_2)_1(_3)_3$ give the following digraph:

We just have to show that the resulting digraph indeed has a unique eulerian circuit (which correspond to the order of the parentheses in the string). Let the string of parentheses have the form $\cdots ?_\ell (_i (_j \cdots )_i ?_k \cdots$, where $?$ represent either a close or open parenthesis. We have to show that if we enter vertex $i$ from $\ell$, we must exit it towards $j$, not $k$. Suppose, for the sake of contradiction, that we exit it towards $k$. Note that, by properties of valid parentheses arrangements, the two parentheses corresponding to vertex $v\ne i$ are either both between $(_i$ and $)_i$ (then we will say that $v$ is of type $A$) or both outside (type $B$). Since $k$ is of type $B$ and the only way to go from a vertex of type $B$ to a vertex of type $A$ is through $i$, we must eventually enter $i$ through a vertex of type $B$ in order to access vertices of type $A$. The only way to do so, however, is through edge $\ell \to i$, which we already used. This is a contradiction, so the uniqueness of the eulerian tour is proved.

Since it is clear that the two maps we described are inverses of each pother, we constructed an explicit bijection between valid edge-pointed digraphs over the vertex set $[n]$ and valid ways to arrange $n$ distinguishable pairs of open/close parentheses, making clear the presence of Catalan numbers. Note that we could also have avoided the identification of an edge of the digraph by considering parentheses strings up to cyclic shift (the property of being a valid parentheses arrangement is invariant by cyclic shift, if we allow ourselves to flip the parentheses so that the first one of each pair is open and the second is closed).