𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Tree-like Properties of Cycle Factorizations

✍ Scribed by Ian Goulden; Alexander Yong

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
125 KB
Volume
98
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

We provide a bijection between the set of factorizations, that is, ordered (n -1)tuples of transpositions in S n whose product is (12...n), and labelled trees on n vertices. We prove a refinement of a theorem of J. Dénes (1959, Publ. Math. Inst. Hungar. Acad. Sci. 4, 63-71) that establishes new tree-like properties of factorizations. In particular, we show that a certain class of transpositions of a factorization corresponds naturally under our bijection to leaf edges (incident with a vertex of degree 1) of a tree. Moreover, we give a generalization of this fact.

📜 SIMILAR VOLUMES

Cycle factorizations of powers of odd cy
Cycle factorizations of powers of odd cycles
✍ S. El-Zanati; C. Vanden Eynden 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 423 KB

Let m ≥ 3 be an odd integer and let k, n, and s ≥ 3 be positive integers. We present sufficient conditions for the existence of Cs-factorizations of (C m k ) n . We show these conditions to be necessary when m is prime.

Hamilton cycle rich two-factorizations o
Hamilton cycle rich two-factorizations of complete graphs
✍ Darryn Bryant 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## Abstract For all integers __n__ ≥ 5, it is shown that the graph obtained from the __n__‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order __n__. This result is used to prove s

List circular coloring of trees and cycl
List circular coloring of trees and cycles
✍ André Raspaud; Xuding Zhu 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB

## Abstract Suppose __G__=(__V__, __E__) is a graph and __p__ ≥ 2__q__ are positive integers. A (__p__, __q__)‐coloring of __G__ is a mapping ϕ: __V__ → {0, 1, …, __p__‐1} such that for any edge __xy__ of __G__, __q__ ≤ |ϕ(__x__)‐ϕ(__y__)| ≤ __p__‐__q__. A color‐list is a mapping __L__: __V__ → $\c

Factorizations and characterizations of
Factorizations and characterizations of induced-hereditary and compositive properties
✍ Alastair Farrugia; Peter Mihók; R. Bruce Richter; Gabriel Semanivšin 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract An Erratum has been published for this article in Journal of Graph Theory 50:261, 2005. A graph property (i.e., a set of graphs) is hereditary (respectively, induced‐hereditary) if it is closed under taking subgraphs (resp., induced‐subgraphs), while the property is additive if it is c