A combinatorial interpretation of the bijection of Goulden and Yong
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2020-01-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1016/j.akcej.2019.03.006 |
| _version_ | 1819122076032696320 |
|---|---|
| author | Kerry Ojakian |
| author_facet | Kerry Ojakian |
| author_sort | Kerry Ojakian |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-22T06:46:42Z |
| format | Article |
| id | doaj.art-e72ea81baec54e1dac87fddade157da0 |
| institution | Directory Open Access Journal |
| issn | 0972-8600 2543-3474 |
| language | English |
| last_indexed | 2024-12-22T06:46:42Z |
| publishDate | 2020-01-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-e72ea81baec54e1dac87fddade157da02022-12-21T18:35:16ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002543-34742020-01-0117142944210.1016/j.akcej.2019.03.0061760638A combinatorial interpretation of the bijection of Goulden and YongKerry Ojakian0Department of Mathematics and Computer Science, Bronx Community College (CUNY), 2155 University AvenueWe 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.http://dx.doi.org/10.1016/j.akcej.2019.03.006factorizationstranspositionsdualbijection |
| spellingShingle | Kerry Ojakian A combinatorial interpretation of the bijection of Goulden and Yong AKCE International Journal of Graphs and Combinatorics factorizations transpositions dual bijection |
| title | A combinatorial interpretation of the bijection of Goulden and Yong |
| title_full | A combinatorial interpretation of the bijection of Goulden and Yong |
| title_fullStr | A combinatorial interpretation of the bijection of Goulden and Yong |
| title_full_unstemmed | A combinatorial interpretation of the bijection of Goulden and Yong |
| title_short | A combinatorial interpretation of the bijection of Goulden and Yong |
| title_sort | combinatorial interpretation of the bijection of goulden and yong |
| topic | factorizations transpositions dual bijection |
| url | http://dx.doi.org/10.1016/j.akcej.2019.03.006 |
| work_keys_str_mv | AT kerryojakian acombinatorialinterpretationofthebijectionofgouldenandyong AT kerryojakian combinatorialinterpretationofthebijectionofgouldenandyong |