TransWikia.com

Digraphs with exactly one Eulerian Tour

Mathematics Asked by Luz Grisales on December 13, 2021

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?

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP