A combinatorial interpretation of the bijection of Goulden and Yong

Abstract

We define a dual of a graph, generalizing the definition of Goulden et al. (2002), which only applies to trees; then we reprove their main result using our new definition. We in fact give two characterizations of the dual: a graph-theoretic one and an algebraic one, showing that they are in fact the same, and are also the same (on trees) as the topological dual developed by Goulden and Yong. Goulden and Yong use their dual to define a bijection between the vertex labeled trees and the factorizations of the permutation into transpositions, showing that their bijection has a particular structural property. We give a combinatorial, non-topological, proof of their result, using our dual.

Keywords

• factorizations
• transpositions
• dual
• bijection