Content area
Abstract
This thesis focuses on determining when a graph with additional structure contains certain subgraphs, particularly circuits, cycles, or trees. The specific problems and presented results include a blend of many fundamental graph theory concepts such as edge-coloring, routing problems, decomposition problems, and containing cycles of various lengths. The three primary chapters in this thesis address the problems of finding eulerian circuits with additional restrictions, decomposing the edge-colored complete graph Kn into rainbow spanning trees, and showing a 4-connected claw-free and N(3,2,1)-free graph is pancyclic.
Let G be an eulerian digraph with a fixed edge coloring (incident edges may have the same color). A compatible circuit of Gis an eulerian circuit such that every two consecutive edges in the circuit have different colors. We characterize the existence of a compatible circuit for digraphs avoiding certain vertices of outdegree three. For certain families of digraphs where all the vertices are of outdegree three we also have a characterization for when there is a compatible circuit. From our characterizations we develop a polynomial time algorithm that determines the existence of a compatible circuit in an edge-colored eulerian digraph and produces a compatible circuit if one exists.
A rainbow spanning tree T is a spanning tree of an edge-colored graph where all the edges of T have different colors. Brualdi and Hollingsworth conjectured that every properly edge-colored K n (n at least 6 and even) using exactly n – 1 colors has n/2 edge-disjoint rainbow spanning trees, and they proved there are at least two edge-disjoint rainbow spanning trees. Kaneko, Kano, and Suzuki strengthened the conjecture to include any proper edge coloring of Kn, and they proved there are at least three edge-disjoint rainbow spanning trees.
We prove that if n is at least 1,000,000 then an edge-colored Kn, where each color appears on at most n/2 edges, contains at least the floor of n/(1000 log n) edge-disjoint rainbow spanning trees.
The final result focuses on showing a 4-connected, claw-free, and N(3,2,1)-free graph is pancyclic. A graph G is pancyclic if it contains cycles of all lengths from 3 to |V( G)|. There has been interest in determining which pairs of forbidden subgraphs imply a 4-connected graph is pancyclic. In the last chapter we present a result that helps complete the classification of which 4-connected, claw-free, and N-free graphs are pancyclic.
