Not every graph has an Eulerian tour. But every finite, strongly connected graph has a 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 tail(e)=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'.
Classification :
05C05, 05C20, 05C30, 05C45, 05C50
Mots-clés :
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
Affiliations des auteurs :
Matthew Farrell
1
;
Lionel Levine
1
1
Cornell University
Matthew Farrell; Lionel Levine. Multi-Eulerian tours of directed graphs. The electronic journal of combinatorics, Tome 23 (2016) no. 2. doi: 10.37236/5588
@article{10_37236_5588,
author = {Matthew Farrell and Lionel Levine},
title = {Multi-Eulerian tours of directed graphs},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {2},
doi = {10.37236/5588},
zbl = {1335.05041},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5588/}
}
TY - JOUR
AU - Matthew Farrell
AU - Lionel Levine
TI - Multi-Eulerian tours of directed graphs
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/5588/
DO - 10.37236/5588
ID - 10_37236_5588
ER -
%0 Journal Article
%A Matthew Farrell
%A Lionel Levine
%T Multi-Eulerian tours of directed graphs
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/5588/
%R 10.37236/5588
%F 10_37236_5588
