\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{graphicx,amsmath,amsthm,verbatim,amssymb,lineno,eucal,titletoc,enumerate} \usepackage{bbm} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \hypersetup{colorlinks} \bibliographystyle{abbrvnat} %\pdfoutput=1 % comment out for arxiv submission % Modified href style \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\Set}[2]{\left\{ #1 \, \left| \; #2 \right. \right\}} \newcommand{\Sett}[2]{\left\{ #1 \; : \; #2 \right\}} \newcommand{\floor}[1]{\left\lfloor {#1} \right\rfloor} \newcommand{\ceiling}[1]{\left\lceil {#1} \right\rceil} \newcommand{\binomial}[2]{\left( \begin{array}{c} {#1} \\ {#2} \end{array} \right)} \newcommand{\modulo}[1]{\quad (\mbox{mod }{#1})} \newcommand{\modnospace}[1]{\; (\mbox{mod }{#1})} \newcommand{\ghost}[1]{\textcolor{white}{#1}} \newcommand{\old}[1]{} \newcommand{\moniker}[1]{{\em (#1)}} \newcommand{\dmoniker}[1]{(#1)} \def\tail{\mathrm{tail}} \def\head{\mathrm{head}} \def\til{\widetilde} \DeclareRobustCommand{\SkipTocEntry}[5]{} \newcommand{\silentsec}[1]{\addtocontents{toc}{\SkipTocEntry}\section*{#1}} % won't appear in TOC \newcommand{\silentsubsec}[1]{\addtocontents{toc}{\SkipTocEntry}\subsection*{#1}} \hyphenation{qua-si-ran-dom} \hyphenation{Schutz-en-ber-ger} \hyphenation{com-mut-at-iv-ity} \newtheorem{thm}{Theorem} \newtheorem{prop}[thm]{Proposition} \newtheorem{proc}[thm]{Procedure} \newtheorem{lem}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{conjecture}[thm]{Conjecture} \theoremstyle{remark} \newtheorem*{remark}{Remark} \newtheorem*{example}{Example} \newcounter{counter} \numberwithin{counter}{section} \theoremstyle{definition} \newtheorem{defn}{Definition} \def\liminf{\mathop{\rm lim\,inf}\limits} \def\mod{\mbox{mod }} \def\isom{\simeq} \def\outdeg{\mbox{outdeg}} \def\indeg{\mbox{indeg}} \def\iindeg{\mbox{\scriptsize indeg}} \def\vertex{\mbox{\scriptsize vertex}} \def\edge{\mbox{\scriptsize edge}} \def\source{s} \def\target{t} \def\ssource{s} \def\ttarget{t} \def\root{{\mbox{\scriptsize root}}} \def\spans{{\scriptsize \mbox{ spans }}} \def\Im{\mbox{Im}} \def\Id{\mbox{Id}} \def\aa{\mathbf{a}} \def\bb{\mathbf{b}} \def\dd{\mathbf{d}} \def\mm{\mathbf{m}} \def\nn{\mathbf{n}} \def\qq{\mathbf{q}} \def\rr{\mathbf{r}} \def\ss{\mathbf{s}} \def\ttt{\mathbf{t}} \def\uu{\mathbf{u}} \def\vv{\mathbf{v}} \def\ww{\mathbf{w}} \def\xx{\mathbf{x}} \def\yy{\mathbf{y}} \def\zz{\mathbf{z}} \def\zero{\mathbf{0}} \def\one{\mathbf{1}} \def\mm{\mathbf{m}} \def\kk{\mathbf{k}} \def\til{\widetilde} \def\Nhood{N} \def\N{\mathbb{N}} \def\Z{\mathbb{Z}} \def\Q{\mathbb{Q}} \def\R{\mathbb{R}} \def\EE{\mathbb{E}} \def\PP{\mathbb{P}} \def\eps{\epsilon} \def\line{\mathcal{L}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\bf Multi-Eulerian tours of directed graphs} \author{Matthew Farrell \qquad Lionel Levine\thanks{Supported by NSF grant \href{http://www.nsf.gov/awardsearch/showAward?AWD_ID=1455272}{DMS-1455272} and a Sloan Fellowship.}\\ \small Department of Mathematics\\[-0.8ex] \small Cornell University\\[-0.8ex] \small Ithaca, New York, U.S.A.\\ \small\tt msf235@cornell.edu\\ \small\tt \url{http://www.math.cornell.edu/~levine} } %% Alternative way to list authors % \author{Matthew Farrell \\ % \small Department of Mathematics\\[-0.8ex] % \small Cornell University\\[-0.8ex] % \small New York, U.S.A.\\ % \small\tt msf235@cornell.edu\\ % \and % Lionel Levine\thanks{Supported by NSF grant \href{http://www.nsf.gov/awardsearch/showAward?AWD_ID=1455272}{DMS-1455272} and a Sloan Fellowship.}\\ % \small Department of Mathematics\\[-0.8ex] % \small Cornell University\\[-0.8ex] % \small New York, U.S.A.\\ % \small\tt levine@math.cornell.edu\\ % } \date{\dateline{24 September 2015. Revised 4 April 2016}{}\\ \small Mathematics Subject Classifications: 05C05, % Trees 05C20, % Directed graphs (digraphs), tournaments 05C30, % Enumeration in graph theory 05C45, % Eulerian and Hamiltonian graphs 05C50} %Graphs and linear algebra (matrices, eigenvalues, etc.) \begin{document} \maketitle \begin{abstract} Not every graph has an Eulerian tour. But every finite, strongly connected graph has a \emph{multi-Eulerian tour}, which we define as a closed path that uses each directed edge at least once, and uses edges $e$ and $f$ the same number of times whenever $\mathrm{tail}(e)=\mathrm{tail}(f)$. This definition leads to a simple generalization of the BEST Theorem. We then show that the minimal length of a multi-Eulerian tour is bounded in terms of the Pham index, a measure of `Eulerianness'. \bigskip\noindent \textbf{Keywords:} BEST theorem, coEulerian digraph, Eulerian digraph, Eulerian path, Laplacian, Markov chain tree theorem, matrix-tree theorem, oriented spanning tree, period vector, Pham index, rotor walk \end{abstract} In the following $G=(V,E)$ denotes a finite directed graph, with loops and multiple edges permitted. %We denote the endpoints of an edge $e \in E$ by $\tail(e)$ and $\head(e)$. An \textbf{Eulerian tour} of $G$ is a closed path that traverses each directed edge exactly once. Such a tour exists only if the indegree of each vertex equals its outdegree; the graphs with this property are called \textbf{Eulerian}. The BEST theorem (named for its discoverers: de Bruijn, Ehrenfest \cite{EdB51}, Smith and Tutte \cite{TS}) counts the number of such tours. The purpose of this note is to generalize the notion of Eulerian tour and the BEST theorem to any finite, strongly connected graph $G$. \begin{defn} Fix a vector $\pi \in \N^V$ with all entries strictly positive. A \textbf{$\pi$-Eulerian tour} of $G$ is a closed path that uses each directed edge $e$ of $G$ exactly $\pi_{\mathrm{tail}(e)}$ times. \end{defn} Note that existence of a $\pi$-Eulerian tour implies that $G$ is \textbf{strongly connected}: for each $v,w \in V$ there are directed paths from $v$ to $w$ and from $w$ to $v$. We will show that, conversely, every strongly connected graph $G$ has a $\pi$-Eulerian tour for suitable $\pi$. To do so, recall the BEST theorem counting $\one$-Eulerian tours of an Eulerian directed multigraph $G$. Write $\eps_\pi(G,e)$ for the number of $\pi$-Eulerian tours of $G$ starting with a fixed edge $e$. \begin{thm} \emph{(BEST \cite{EdB51,TS})} %\cite[\textsection 5.6]{Stanley} A strongly connected multigraph $G$ has a $\one$-Eulerian tour if and only if the indegree of each vertex equals its outdegree, in which case the number of such tours starting with a fixed edge $e$ is \[ \eps_\one(G,e) = \kappa_w \prod_{v \in V} (d_v -1)! \] where $d_v$ is the outdegree of $v$; vertex $w$ is the tail of edge $e$, and $\kappa_w$ is the number of spanning trees of $G$ oriented toward $w$. \end{thm} A \textbf{spanning tree oriented toward $w$} is a set of edges $t$ such that $w$ has outdegree $0$ in $t$, each vertex $v \neq w$ has outdegree $1$ in $t$, and $t$ has no directed cycles. Let us remark that for a general directed graph the number $\kappa_w$ of spanning trees oriented toward $w$ depends on $w$, but for an Eulerian directed graph it does not (since $\eps_\one(G,e)$ does not depend on $e$). The \textbf{graph Laplacian} is the $V \times V$ matrix \[ \Delta_{uv} = \begin{cases} d_v - d_{vv}, & u=v \\ -d_{vu} & u \neq v \end{cases} \] where $d_{vu}$ is the number of edges directed from $v$ to $u$, and $d_v = \sum_u d_{vu}$ is the outdegree of $v$. By the matrix-tree theorem \cite[5.6.8]{Stanley}, $\kappa_w$ is the determinant of the submatrix of $\Delta$ omitting row and column $w$. Thus, the BEST and matrix-tree theorems give a computationally efficient exact count of the $\one$-Eulerian tours of a directed multigraph. (In contrast, exact counting of \emph{undirected} Eulerian tours is a \#P-complete problem!) Observing that the `indegree$=$outdegree' condition in the BEST theorem is equivalent to $\Delta \one = \zero$ where $\one$ is the all ones vector, we arrive at the statement of our main result. \begin{thm} \label{t.BETTER} Let $G=(V,E)$ be a strongly connected directed multigraph with Laplacian $\Delta$, and let $\pi \in \N^V$. Then $G$ has a $\pi$-Eulerian tour if and only if \[ \Delta \pi = \zero. \] If $\Delta \pi = \zero$, then the number of $\pi$-Eulerian tours starting with edge $e$ is given by \[ \epsilon_\pi(G,e)= \kappa_w \prod_{v\in V} \frac {(d_{v}\pi_v-1)!}{(\pi_v!)^{d_{v}-1}(\pi_v-1)!} \] where $d_v$ is the outdegree of $v$; vertex $w$ is the tail of edge $e$, and $\kappa_w$ is the number of spanning trees of $G$ oriented toward $w$. \end{thm} Note that the ratio on the right side is a multinomial coefficient and hence an integer. The proof below is a straightforward application of the BEST theorem. The same proof device of constructing an Eulerian multigraph from a strongly connected graph was used in \cite[Theorem~3.18]{AB} to relate the Riemann-Roch property of `row chip-firing' to that of `column chip-firing'. In the remainder of the paper we find the length of the shortest $\pi$-Eulerian tour (Theorem~\ref{t.minimal}) %, relate $\eps_\pi(G,e)$ to the total number of $\pi$-Eulerian tours (Theorem~\ref{t.ratio}) and conclude with two mild generalizations: $\lambda$-Eulerian tours (Theorem~\ref{t.lambda}) and $\pi$-Eulerian paths (Theorem~\ref{t.path}). \begin{proof}[Proof of Theorem~\ref{t.BETTER}] Define a multigraph $\til{G}$ by replacing each edge $e$ of $G$ from $u$ to $v$ by $\pi_u$ edges $e^1,\ldots,e^{\pi_u}$ from $u$ to $v$. Since $\pi$ has all positive entries, $\til G$ is strongly connected. Each vertex $v$ of $\til{G}$ has outdegree $d_v \pi_v$ and indegree $\sum_{u \in V} \pi_u d_{uv}$, so $\til{G}$ is Eulerian if and only if $\Delta \pi = \zero$. If $(e_1^{i_1}, \ldots, e_m^{i_m})$ is a $\one$-Eulerian tour of $\til{G}$, then $(e_1, \ldots, e_m)$ is a $\pi$-Eulerian tour of $G$. Conversely, for each $\pi$-Eulerian tour of $G$, %beginning with a fixed edge $e$, the occurrences of each edge $f$ in the tour can be labeled with an arbitrary permutation of $\{1,\ldots,\pi_{\mathrm{tail}(f)}\}$ to obtain a $\one$-Eulerian tour of $\til G$. %beginning with one of $e^1, \ldots, e^{\pi_{\tail(e)}}$. Hence for a fixed edge $e$ with $\tail(e)=w$, \[ \eps_\pi(G,e) \prod_{v \in V} (\pi_v!)^{d_v} = \eps_\one(\til{G},e^1) \pi_{w}. \] The factor of $\pi_{w}$ arises here from the label of the starting edge $e$, and the observation that $\eps_\one(\til{G},e^i)$ does not depend on $i$. In particular, $G$ has a $\pi$-Eulerian tour if and only if $\til G$ is Eulerian. To complete the counting in the case when $\til G$ is Eulerian, the BEST theorem gives the number of $\one$-Eulerian tours of $\til{G}$ starting with $e^1$, namely \[ \eps_\one(\til{G},e^1) = \til{\kappa}_w \prod_{v \in V} (d_v \pi_v - 1)! \] where \begin{equation} \label{e.tildekappa} \til \kappa_w = \kappa_w \prod_{v \neq w} \pi_v \end{equation} is the number of spanning trees of $\til G$ oriented toward $w$, since each spanning tree of $G$ oriented toward $w$ gives rise to $\prod_{v \neq w} \pi_v$ spanning trees of $\til G$. We conclude that \begin{align*} \eps_\pi(G,e) %&= \eps(\til{G},e^1) \pi_w \prod_{v \in V} (\pi_v !)^{-d_v} \\ &= \pi_w \til{\kappa}_w \prod_{v \in V} \frac{(d_v \pi_v -1)!}{(\pi_v !)^{d_v}} \end{align*} which together with \eqref{e.tildekappa} completes the proof. \end{proof} The watchful reader must now be wondering, is there a suitable vector $\pi$ with \emph{positive integer} entries in the kernel of the Laplacian? The answer is yes. Following Bj\"{o}rner and Lov\'{a}sz, we say that a vector $\mathbf{p} \in \N^V$ is a \textbf{period vector} for $G$ if $\mathbf{p} \neq \zero$ and $\Delta\mathbf{p}=\zero$. A period vector is \textbf{primitive} if the greatest common divisor of its entries is $1$. \old{ \begin{defn} \cite{BL92} Given a graph $G$ with Laplacian $\Delta$, a vector $\mathbf{p}\in\mathbb{N}^{n}$ is called a \textbf{period vector} for $G$ if $\mathbf{p} \neq \zero$ and $\Delta\mathbf{p}=\zero$. A period vector is \textbf{primitive} if the greatest common divisor of its entries is $1$. \end{defn} The following lemma sums up some useful properties of period vectors. } \begin{lem} \cite[Prop.\ 4.1]{BL92} \label{lem:period} A strongly connected multigraph $G$ has a unique primitive period vector $\pi_{G}$. All entries of $\pi_G$ are strictly positive, and all period vectors of $G$ are of the form $n\pi_{G}$ for $n=1,2,\ldots$. Moreover, if $G$ is Eulerian, then $\pi_{G}=\mathbf{1}$. \end{lem} Recall $\kappa_v$ denotes the number of spanning trees of $G$ oriented toward $v$. Broder \cite{Broder} and Aldous \cite{Aldous} observed that $\kappa = (\kappa_v)_{v \in V}$ is a period vector! This result is sometimes called the `Markov chain tree theorem'. %because it implies that by recording the most recent exit of a random walk from each vertex, one obtains a Markov chain on oriented spanning trees, whose stationary distribution is proportional to uniform after conditioning on the root of the tree (=location of the walker). \begin{lem}[\cite{Aldous,Broder}] \label{lem:kerper} $\Delta \kappa = \zero$. \end{lem} Lemmas \ref{lem:period} and \ref{lem:kerper} imply that the vector $\pi=\frac{1}{M_G} \kappa$ is the unique primitive period vector of $G$, where \[ M_G = \gcd \{ \kappa_v \,:\, v \in V\} \] is the greatest common divisor of the oriented spanning tree counts. Our next result expresses the minimal length of a multi-Eulerian tour in terms of $M_G$ and the number \[ U_G = \sum_{v \in V} \kappa_v d_v \] of \textbf{unicycles} in $G$ (that is, pairs $(t,e)$ where $t$ is an oriented spanning tree and $e$ is an outgoing edge from the root of $t$). \begin{thm} \label{t.minimal} The minimal length of a multi-Eulerian tour in a strongly connected multigraph $G$ is $U_G/M_G$. \end{thm} \begin{proof} The length of a $\pi$-Eulerian tour is $\sum_{v \in V} \pi_v d_v$. By Theorem~\ref{t.BETTER} along with Lemmas~\ref{lem:period} and~\ref{lem:kerper}, there exists a $\pi$-Eulerian tour if and only if $\pi$ is a positive integer multiple of the primitive period vector $\frac{1}{M_G} \kappa$. The result follows. \end{proof} A special class of multi-Eulerian tours are the simple rotor walks \cite{PDDK,WLB,HLMPPW,HP,Trung}. In a \textbf{simple rotor walk}, the successive exits from each vertex repeatedly cycle through a given cyclic permutation of the outgoing edges from that vertex. If $G$ is Eulerian then a simple rotor walk on $G$ eventually settles into an Eulerian tour which it traces repeatedly. More generally, if $G$ is strongly connected then a simple rotor walk eventually settles into a $\pi$-Eulerian tour where $\pi$ is the primitive period vector of $G$. Trung Van Pham introduced the quantity $M_G$ in \cite{Trung} in order to count orbits of the rotor-router operation. In \cite{coEulerian} we have called $M_G$ the \textbf{Pham index} of $G$ and studied the graphs with $M_G=1$, which we called \textbf{coEulerian graphs}. The significance of $M_G$ is not readily apparent from its definition, but we argue in \cite{coEulerian} that $M_G$ measures `Eulerianness'. Theorem~\ref{t.minimal} makes this explicit, in that the minimal length of a multi-Eulerian tour depends inversely on $M_G$. A consequence of Theorem~\ref{t.BETTER} is that the number of $\pi$-Eulerian tours beginning with edge $e$ does not depend on $\head(e)$. This can also be proved directly by cycling the tour to relate the number of tours starting with edge $e$ to the total number of $\pi$-Eulerian tours: \[ \eps_\pi(G,e) = \frac{\pi_{\tail(e)} \sum_{f \in E} \eps_\pi(G,f)}{\sum_{v \in V} \pi_v d_v }. \] \old{ \begin{thm} \label{t.ratio} Writing $\eps_\pi(G) = \sum_{e \in E} \eps_\pi(G,e)$, we have for all $e \in E$ \[ \eps_\pi(G,e) = \eps_\pi(G) \frac{\pi_{\tail(e)}}{\sum_{v \in V} \pi_v d_v }. \] \end{thm} \begin{proof} %If $\gamma, \gamma'$ are $\pi$-Eulerian tours starting with edges $e,e'$ respectively, write $\gamma \equiv \gamma'$ if $\gamma'$ is a cyclic shift of $\gamma$. If $\gamma$ is a $\pi$-Eulerian tour of $G$ (with a fixed starting edge) then each cyclic shift of $\gamma$ is a $\pi$-Eulerian tour (with a possibly different starting edge). Write $[\gamma]$ for the set of all cyclic shifts of $\gamma$. Let $\ell = \# [\gamma]$ be the number of distinct cyclic shifts and let $L = \sum_{v \in V} \pi_v d_v$. Then $\gamma$ consists of $L/\ell$ repetitions of some tour %$\gamma_1$ of length $\ell$. Since $\gamma$ is $\pi$-Eulerian, each edge $e$ of $G$ appears $\pi_{\tail(e)}$ times in $\gamma$. %, hence $(m/M) \pi_{\tail(e)}$ times in $\gamma_1$. % (In particular, if $\gcd(\pi_v) = 1$ then $m=M$.) Among the $\ell$ distinct cyclic shifts of $\gamma$, exactly $(\ell/L)\pi_{\tail(e)}$ begin with edge $e$. Hence \[ \eps_\pi(G,e) = \sum_{[\gamma]} \frac{\# [\gamma]}{L} \pi_{\tail(e)} \] where the sum is over equivalence classes of $\pi$-Eulerian tours of $G$ up to cyclic shift. The proof is completed by observing that $\sum_{[\gamma]} \# [\gamma] = \eps_\pi(G)$. \end{proof} } We thank an anonymous referee for pointing out that the proof method of Theorem~\ref{t.BETTER} also gives an efficient count of certain more general tours. \begin{defn} Fix a vector $\lambda \in \N^E$ with all entries strictly positive. A \textbf{$\lambda$-Eulerian tour} is a closed path that uses each directed edge $e$ exactly $\lambda(e)$ times. \end{defn} \begin{thm} \label{t.lambda} Let $G=(V,E)$ be a strongly connected directed multigraph, and let $\lambda \in \N^E$. Then $G$ has a $\lambda$-Eulerian tour if and only if \begin{equation} \label{e.tildeeulerian} \sum_{\tail(e)=v} \lambda_e = \sum_{\head(e)=v} \lambda_e \qquad\qquad \text{\em for all } v \in V. \end{equation} If $G$ has a $\lambda$-Eulerian tour, then the number of $\lambda$-Eulerian tours starting with a fixed edge $e$ with tail $w$ is \[ \det \til \Delta_w \frac{ \lambda_e \prod_{v \in V} (\til d_v-1)!}{ \prod_{f \in E} (\lambda_f)!} \] where $\til \Delta_w$ is the submatrix omitting row and column $w$ of the Laplacian of the multigraph $\til G$ obtained by replacing each edge $e$ of $G$ from $u$ to $v$ by $\lambda_e$ edges $e^1,\ldots,e^{\lambda_e}$ from $u$ to $v$; and $\til d_v = \sum_{\tail(e)=v} \lambda_e$ is the degree of $v$ in $\til G$. \end{thm} \begin{proof} %Each vertex $v$ of $\til{G}$ has outdegree $\sum_{\tail(e)=v} \lambda_e$ and indegree $\sum_{\head(e)=v} \lambda_e$, so %$\til{G}$ is Eulerian if and only if \eqref{e.tildeeulerian} holds. % If $(e_1^{i_1}, \ldots, e_\ell^{i_\ell})$ is a $\one$-Eulerian tour of $\til{G}$, then $(e_1, \ldots, e_\ell)$ is a $\lambda$-Eulerian tour of $G$. Conversely, for each $\lambda$-Eulerian tour of $G$, %beginning with a fixed edge $e$, the occurrences of each edge $f$ in the tour can be labeled with an arbitrary permutation of $\{1,\ldots,\lambda_f\}$ to obtain a $\one$-Eulerian tour of $\til G$. %beginning with one of $e^1, \ldots, e^{\pi_{\tail(e)}}$. Hence for a fixed edge $e$ with $\tail(e)=w$, \[ \eps_\lambda(G,e) \prod_{f \in E} (\lambda_f)! = \eps_\one(\til{G},e^1) \lambda_{e}. \] %The factor of $\lambda_{e}$ arises here from the label of the starting edge $e$, and the observation that $\eps_\one(\til{G},e^i)$ does not depend on $i$. In particular, $G$ has a $\lambda$-Eulerian tour if and only if $\til G$ is Eulerian, which happens if and only if \eqref{e.tildeeulerian} holds. % To complete the counting in the case when $\til G$ is Eulerian, the BEST theorem gives the number of $\one$-Eulerian tours of $\til{G}$ starting with $e^1$, namely \[ \eps_\one(\til{G},e^1) = \det \til \Delta_w \prod_{v \in V} (\til d_v - 1)! \] where $\det \til \Delta_w$ is the number of spanning trees of $\til G$ oriented toward $w$ by the matrix-tree theorem. \end{proof} So far we have assumed that $G$ is strongly connected. % and there is no loss in doing so, since existence of a $\pi$-Eulerian tour of $G$ implies that $G$ is strongly connected. For our last result we drop this assumption, and count $\pi$-Eulerian paths which are permitted to start and end at different vertices. \begin{defn} Fix $\pi \in \N^V$ with all entries strictly positive, and vertices $a,z \in V$. A \textbf{$\pi$-Eulerian path} from $a$ to $z$ is a path $a=e_1, \ldots, e_m=z$ in which each edge $e$ appears exactly $\pi_{\tail(e)}$ times. \end{defn} \begin{thm} \label{t.path} Let $G=(V,E)$ be a directed multigraph with Laplacian $\Delta$, let $\pi \in \N^V$ and fix vertices $a \neq z $. Then $G$ has a $\pi$-Eulerian path from $a$ to $z$ if and only if $(V,E \cup {(z,a)})$ is strongly connected and \[ \Delta \pi = 1_a - 1_z. \] If $G$ has a $\pi$-Eulerian path from $a$ to $z$, then the number of such paths is \begin{equation} \label{e.pieulpath} \epsilon_\pi(G,a \to z)= \kappa_z \, \frac{(d_z \pi_z)!}{(\pi_z)!^{d_z}} \prod_{v \in V-\{z\}} \frac{(d_{v}\pi_v-1)!}{(\pi_v!)^{d_{v}-1}(\pi_v -1)!}. \end{equation} %where $d_v$ is the outdegree of $v$; vertex $w$ is the tail of edge $e$, and $\kappa_w$ is the number of spanning trees of $G$ oriented toward $w$. \end{thm} \begin{proof} Let $G'$ be the multigraph obtained from $G$ by adding a new vertex $w$ with one edge $(z,w)$, one edge $(w,a)$ and $\pi_z - 1$ edges $(w,z)$. Set $\pi_w=1$. Given a $\pi$-Eulerian tour of $G'$, omitting all edges incident to $w$ yields a $\pi$-Eulerian path from $a$ to $z$ in $G$. Conversely, any $\pi$-Eulerian path from $a$ to $z$ in $G$ can be augmented to a $\pi$-Eulerian tour of $G'$ beginning with the edge $(w,a)$ (and necessarily ending with edge $(z,w)$) by inserting $\pi_z-1$ detours from $z$ to $w$ and back. (Here we have used $a \neq z$; in the case $a=z$ we would need to set $\pi_w=\pi_z$.) This insertion can be performed in ${d_z \pi_z + \pi_z - 1 \choose \pi_z -1} (\pi_z - 1)!$ possible ways. %(Here we we use that the tour is primitive, since $\pi_w=1$.) Hence \[ \eps_\pi(G',(w,a)) = \eps_\pi(G,a \to z) \binomial{d_z \pi_z + \pi_z - 1}{\pi_z -1} (\pi_z - 1)!. \] In particular, $G$ has a $\pi$-Eulerian path from $a$ to $z$ if and only if $G'$ has a $\pi$-Eulerian tour. By Theorem~\ref{t.BETTER}, this happens if and only if $G'$ is strongly connected and $\Delta' \pi = \zero$, where $\Delta'$ is the Laplacian of $G'$; equivalently, $(V,E\cup (z,a))$ is strongly connected and $\Delta \pi = 1_a - 1_z$. For the count, since the spanning trees of $G'$ oriented toward $w$ are in bijection with the spanning trees of $G$ oriented toward $z$, we obtain from Theorem~\ref{t.BETTER} \[ \eps_\pi(G',(w,a)) = \kappa_z \prod_{v \in V \cup \{w\}} \frac{(d'_{v}\pi_v-1)!}{(\pi_v!)^{d'_{v}-1} (\pi_v-1)!} \] where $d'_v$ is the outdegree of $v$ in $G'$. For $v \notin \{w,z\}$ we have $d'_v=d_v$. Since $d'_w=\pi_z$ and $\pi_w = 1$, the ratio on the right side is just $(\pi_z-1)!$ when $v=w$. Since $d'_z = d_z+1$, we end up with \[ \eps_\pi(G,a \to z) = \kappa_z {\binomial{d_z \pi_z + \pi_z - 1}{\pi_z -1}}^{-1} \frac{(d_z \pi_z + \pi_z -1)!}{(\pi_z!)^{d_z} (\pi_z-1)!} \prod_{v \in V-\{z\}} \frac{(d_{v}\pi_v-1)!}{(\pi_v!)^{d_{v}-1}(\pi_v -1)!} \] which simplifies to \eqref{e.pieulpath}. \end{proof} \begin{thebibliography}{9} \bibitem{Aldous} David Aldous, The random walk construction of uniform spanning trees and uniform labelled trees. \emph{SIAM J. Disc.\ Math.} \textbf{3} 450--465, 1990. \bibitem{AB} Arash Asadi and Spencer Backman, Chip-firing and Riemann-Roch theory for directed graphs, \emph{Electronic Notes Discrete Math.} \textbf{38}:63--68, 2011. \arxiv{1012.0287} \bibitem{Broder} Andrei Broder, Generating random spanning trees. \emph{Foundations of Computer Science}, 30th Annual Symposium on, pages 442--447. IEEE, 1989. \bibitem{EdB51} T. van Aardenne-Ehrenfest and N. G. de Bruijn, Circuits and trees in oriented linear graphs, \emph{Simon Stevin} \textbf{28}, 203--217, 1951. \bibitem{BL92} Anders Bj\"{o}rner and L\'{a}szl\'{o} Lov\'{a}sz, Chip-firing games on directed graphs, \emph{J. Algebraic Combin.} Vol 1. 305-328, 1992. \bibitem{coEulerian} Matthew Farrell and Lionel Levine, CoEulerian graphs, \emph{Proc.\ Amer.\ Math.\ Soc.}, to appear, 2015. \arxiv{1502.04690} \bibitem{HLMPPW} Alexander E. Holroyd, Lionel Levine, Karola M\'{e}sz\'{a}ros, Yuval Peres, James Propp and David B. Wilson, Chip-firing and rotor-routing on directed graphs, \emph{In and Out of Equilibrium 2,} \emph{Progress in Probability}, Vol. 60, 331--364, 2008. \arxiv{0801.3306}. \bibitem{HP} Alexander E. Holroyd and James G. Propp, Rotor walks and Markov chains, in \emph{Algorithmic Probability and Combinatorics}, American Mathematical Society, 2010. \arxiv{0904.4507} \bibitem{PDDK} V. B. Priezzhev, Deepak Dhar, Abhishek Dhar and Supriya Krishnamurthy, Eulerian walkers as a model of self-organised criticality, \emph{Phys.\ Rev.\ Lett.} \textbf{77}:5079--5082, 1996. \arxiv{cond-mat/9611019} \bibitem{Stanley} Richard P. Stanley, {\it Enumerative Combinatorics}, vol.\ 2, Cambridge University Press, 1999. \bibitem{Trung} Trung Van Pham, Orbits of rotor-router operation and stationary distribution of random walks on directed graphs, \emph{Adv.\ Applied Math.} \textbf{70}:45--53, 2015. \arxiv{1403.5875} \bibitem{TS} W.T. Tutte and C.A.B. Smith, On unicursal paths in a network of degree 4. \emph{Amer.\ Math.\ Monthly}: 233--237, 1941. \bibitem{WLB} Israel A. Wagner, Michael Lindenbaum and Alfred M. Bruckstein, Smell as a computational resource --- a lesson we can learn from the ant, \emph{4th Israeli Symposium on Theory of Computing and Systems}, pages 219--230, 1996. \end{thebibliography} \end{document}