This Is AuburnElectronic Theses and Dissertations

Show simple item record

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


Metadata FieldValueLanguage
dc.contributor.advisorRodger, Chris
dc.contributor.authorPerry, Katherine
dc.date.accessioned2017-04-26T14:50:08Z
dc.date.available2017-04-26T14:50:08Z
dc.date.issued2017-04-26
dc.identifier.urihttp://hdl.handle.net/10415/5716
dc.description.abstractThis 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.en_US
dc.rightsEMBARGO_NOT_AUBURNen_US
dc.subjectMathematics and Statisticsen_US
dc.titleRainbow Trees in Edge-Colored Complete Graphs and Block Decompositions of Almost Complete Graphsen_US
dc.typePhD Dissertationen_US
dc.embargo.lengthMONTHS_WITHHELD:12en_US
dc.embargo.statusEMBARGOEDen_US
dc.embargo.enddate2018-04-03en_US

Files in this item

Show simple item record