Spanning Trees Orthogonal to One-Factorizations of \(K_{2n}\)

John Krussel1, Susan Marshall2, Helen Verrall3
1Department of Mathematical Sciences Lewis and Clark College Portland, Oregon 97219
2Equipe Combinatoire, Université de Paris VI 4, Place Jussieu 75252 Paris Cedex
3Department of Mathematics and Statistics Simon Fraser University Burnaby, British Columbia V5A 1S6

Abstract

In [3] Brualdi and Hollingsworth conjectured that for any one-factorization \(\mathcal{F}\) of \(K_n\), there exists a decomposition of \(K_{2n}\) into spanning trees orthogonal to \(\mathcal{F}\). They also showed that two such spanning trees always existed. We construct three such trees and exhibit an infinite class of complete graphs with an orthogonal decomposition into spanning trees with respect to the one-factorization \(GK_{2n}\).