pith. sign in

arxiv: 1509.06237 · v1 · pith:FP3RICOZnew · submitted 2015-09-21 · 🧮 math.CO

Multi-Eulerian tours of directed graphs

classification 🧮 math.CO
keywords multi-euleriantourdirectedeverygraphtailusesbest
0
0 comments X
read the original 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'.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.