\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.21}{23(2)}{2016}


\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, USA\\
\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{Sep 24, 2015}{Apr 14, 2016}{Apr 29, 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}{99}

\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}

