<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volumn 9 Issue 2" %>
Colorful Isomorphic Spanning Trees in Complete Graphs
Gregory M. Constantine
Department of Mathematics, University of Pittsburgh, Pittsburgh, PA 15260, USA
Annals of Combinatorics9 (2) p.163-167 June, 2005
AMS Subject Classification: 05C15, 05C05
Can a complete graph on an even number n (> 4) of vertices be properly edge-colored with n - 1 colors in such a way that the edges can be partitioned into edge-disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n - 1 colors occur among its edges. It is proved that this is possible to accomplish whenever n is a power of two.
Keywords: colorful tree, orthogonal Latin squares, colorful matching


1. D. Banks, G. Constantine, A. Merriwether, and R. LaFrance, Nonparametric inference on mtDNA mismatches, J. Nonparametr. Statist. 11 (1999) 215--232.

2. R.B. Bapat, Mixed discriminants and spanning trees, Sankhy¨¡ Ser. A 54 (1992) 49--55.

3. R.B. Bapat and G.M. Constantine, An enumerating function for spanning forests with color restrictions, Linear Algebra Appl. 173 (1992) 231--237.

4. C. Berge, Principles of Combinatorics, Academic Press, New York, 1971.

5. R.C. Bose, S.S. Shrikhande, and E.T. Parker, Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler's conjecture, Canad. J. Math. 12 (1960) 189--203.

6. H. Broersma and X. Li, Spanning trees with many of few colors in edge-colored graphs, Discuss. Math. Graph Theory 17 (2) (1997) 259--269.

7. P.J. Cameron, Parallelisms of complete designs, In: London Math. Soc. Lecture Notes Series, 23, Cambridge Univ. Press, 1976.

8. F. Harari, Parallel concepts in graph theory, Math. Comput. Modelling 18 (7) (1993) 101--105.

9. Q.Z. Liu and H.P. Yap, Edge colorings of K2n with a prescribed condition, Discrete Math. 212 (3) (2000) 233--244.