Rainbow Trees in Edge-Colored Complete Graphs and Block Decompositions of Almost Complete Graphs

Abstract

This dissertation focuses on two problems, the first involving the existence of many edge-disjoint rainbow spanning trees in edge-colored complete graphs, and the second, creating a balanced sampling plan for a two-dimensional array, excluding contiguous units.

A spanning tree of a properly edge-colored complete graph, $K_n$, is rainbow provided that no two different edges in the tree bear the same color. In 1996, Brualdi and Hollingsworth conjectured that if $K_{2m}$ is properly $(2m-1)$-edge-colored, then the edges of $K_{2m}$ can be partitioned into $m$ rainbow spanning trees except when $m=2$. The existence of $\lfloor m/(500 \log(2m)) \rfloor$ mutually edge-disjoint spanning trees in the case that $m\geq 500,000$ was recently proved using probabilistic techniques. By means of an explicit, constructive approach, we construct $\lfloor \sqrt{6m+9}/3 \rfloor$ mutually edge-disjoint rainbow spanning trees for any positive value of $m$. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees. It also improves upon the probabilistic result for all $m$ at most $5.7 \times 10^7$.

Balanced sampling plans excluding contiguous units (BSECs) were first introduced by Hedayat, Rao, and Stufken in 1988. The idea of generalizing this definition to two dimensions was first formalized by Bryant, Chang, Rodger, and Wei in 2002 where the case for block size $3$ and $\lambda = 1$ (the number of blocks each pair of points appears in together) was completely solved. These designs are useful for items arranged in a two-dimensional array where contiguous units provide similar information. In this dissertation, a complete solution for the existence of two-dimensional BSECs with block size $3$ and $\lambda = 3$ is provided.