Multi-Eulerian Tours of Directed Graphs

  • Matthew Farrell
  • Lionel Levine
DOI: https://doi.org/10.37236/5588
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

Abstract

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'.
Published
2016-04-29
Issue
Volume 23, Issue 2 (2016)
Article Number
P2.21