A Bijection for Eulerian-equivalence Classes of Totally Cyclic Orientations

摘要

Gioan showed that the number of cycle reversing classes of totally cyclic orientations of a given graph can be calculated as an evaluation of the corresponding Tutte polynomial. We note that the concept of cycle reversing classes of orientations coincides with that of Eulerian-equivalence classes considered by Chen and Stanley, and Kochol. Based on this coincidence, we give a bijective proof of Gioan’s result. Precisely, the main result of the paper is an algorithmic bijection between the set of Eulerian-equivalence classes of totally cyclic orientations and the set of spanning trees without internally active edges.