2
$\begingroup$

In R.P. Stanley's book, Enumerative Combinatorics, Vol.2, paragraph 5.6, there is an intuitive proof of the BEST therem, which states that the number of eulerian tours in a balanced digraph $D$ with vertices in $V$ is given by

$\epsilon(D) = t(D) \prod_{v' \in V} (\mathrm{out}_{v'}(D)-1)!$

Here $\mathrm{out}_u(D)$ is the outdegree of a vertex, which equals the indegree $\mathrm{in}_u(D)$, and $t(D)$ is the number of arborescences, or spanning oriented rooted trees, which for balanced digraphs turns out to be independent of the root.

I was looking for a generalization to eulerian paths with open ends. Since such paths have to be drawn without lifting the pencil, the balanced digraph on which they take place must have all balanced vertices but for two vertices $u$ and $v$ (respectively the starting and the arrival vertices), such that

$\mathrm{out}_u(D) - \mathrm{in}_u(D)=+1, \quad \mathrm{out}_v(D) - \mathrm{in}_v(D)=-1$.

Now, it seems to me that Stanley's proof works out equally well, I can't see any obvious impediment, so that one should end up with a formula like

$\epsilon_{v,u}(D) = t_v(D) \prod_{v' \in V} (\mathrm{out}_{v'}(D)-1)!$

where now, since the graph is unbalanced, $t_v(D)$ will depend on the root. However, I couldn't find references for this, and the dedicated literature on eulerian trials seems to worried with other kinds of problems, which I have no intuition of. What do you think?

Improve this question
$\endgroup$
3
  • $\begingroup$ Try drawing a line segment between the two unbalanced vertices, and then use the previous result. Gerhard "The Shortest Distance Between Results..." Paseman, 2011.07.01 $\endgroup$
    – Gerhard Paseman
    Commented Jul 1, 2011 at 20:21
  • $\begingroup$ Re the rendition of the original BEST theorem (I am not speaking about the proposed variant here), in particular re "in a balaced digraph" in the OP: to me it seems an underappreciated fact(or at least, drowned-in-the-usual-terminological-confusion-about-what-"digraph"-means-precisely fact) that the BEST theorem is true for every degree-balanced finite quiver. That is, multiple arcs and loops are allowed. $\endgroup$
    – Peter Heinig
    Commented Aug 18, 2017 at 14:05
  • $\begingroup$ Already van Aardenne-Ehrenfest and de Bruijn in page 207 of their original paper are very explicit about allowing quivers (without using that term, of course). Also, a wonderfully detailed exposition of Paul Klingsberg seems useful to point out here. $\endgroup$
    – Peter Heinig
    Commented Aug 18, 2017 at 14:06

1 Answer 1

Reset to default
1
$\begingroup$

The question seems to be sinking into the depths of Lethe; here is a styrofoam noodle for it.

Every Eulerian path on G can be completed to an Eulerian tour on G' which is G augmented with the edge (v,u). This correspondence is easily seen to be 1-1, so the number of desired paths on G is the formula you mention above, applied to the graph G'.

Unless I'm misunderstanding something, that should do it.

Gerhard "Email Me About System Design" Paseman, 2011.07.05

Improve this answer
$\endgroup$
4
  • $\begingroup$ It seems to work. Then my formula is wrong, since deletion-contraction formulas for $t_v(G')$ imply that I'm forgetting a piece; I'll have to make up my mind where Stanley's proof fails for unbalanced digraphs. $\endgroup$
    – tomate
    Commented Jul 6, 2011 at 8:21
  • $\begingroup$ Sleep on it for a night. If it still doesn't work out tomorrow, try a new question to ask for help with the sticky bits. Gerhard "Email Me About System Design" Paseman, 2011.07.06 $\endgroup$
    – Gerhard Paseman
    Commented Jul 6, 2011 at 8:30
  • $\begingroup$ Wait, now I see why this is wrong. It's not true that the correspondence is 1-1. Eulerian paths on G with open ends are 1-1 with those eulerian cycles on G+(v,u) whose final edge is (v,u)! But internal cycles in an eulerian cycle can be walked in any desired order! I'm more and more convinced that my guess is correct. $\endgroup$
    – tomate
    Commented Jul 22, 2011 at 13:34
  • $\begingroup$ I am not sure what you are counting. The edge removal does matter if you are counting a traversal of an Eulerian tour with a given start/endpoint. If you consider two traversals equivalent if the sequence of edges traveled differs by a cyclic permutation, then I think the (set of) equivalence classes of traversals is equinumerous with the paths. If you make clear what is being counted (I thought it was equiv. classes), then I may adjust my answer as needed. Gerhard "Ask Me About System Design" Paseman, 2011.07.22 $\endgroup$
    – Gerhard Paseman
    Commented Jul 22, 2011 at 23:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .