Multi-Eulerian Tours of Directed Graphs

Matthew Farrell, Lionel Levine

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'.

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

Full Text: PDF