1
$\begingroup$

I would like to know if there exists a result saying that for a fixed undirected rooted Eulerian graph, up to some permutation, along any Eulerian cycle, there exists a unique sequence of degrees, where the degree of a vertex along an Eulerian path is (not the usual degree but) the number of neighboor vertices such that the path may be extended to an Eulerian cycle.

As an example, if we consider the graph composed of two vertices (one being the root) linked by $n$ parallel lines of $m_i$ edges each, then up to some permutation the only sequance of degrees along an Eulerian cycle is $(n,n-1,\dots,2,1,\dots,1)$ with $1$ appearing $\sum_{i=1}^n(m_i-1)+1$ times at the end.

$\endgroup$
2
$\begingroup$

Consider the following variation of your example: Start with $3$ vertices, $v_1,v_2,v_3$ and add four common neighbours of $v_1$ and $v_2$ and two common neighbours of $v_2$ and $v_3$. Pick $v_1$ as your root.

In this graph there are (up to isomorphism) two Eulerian walks starting at $v_1$: in the third step you can either choose to continue towards $v_3$, or walk back to $v_1$ first. The first option yields the sequence $$ (4,1,5,1,1,1,3,1,2,1,1,1), $$ the second one gives $$ (4,1,5,1,2,1,\mathbf{2},1,1,1,1,1), $$ where the bold $2$ is due to the fact that if you don't continue towards $v_3$ at this step, then you won't get a Eulerian cycle.

On the other hand, if you count the number of edges incident to the current vertex which have not been used in the walk so far (regardless of whether they can be used to continue the Euler tour), then the sequence is clearly invariant of the chosen Euler tour up to permutation: simply consider the contribution of each vertex individually.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.