Michigan Technological University
On graph decompositions: Exploring the stars and stripes problem with odd n-stars
Abstract
dc:description.abstractThis dissertation addresses the “Stars and Stripes" problem, which is a graph decomposition problem. The Stars and Stripes problem can be described as finding uniformly resolvable decompositions when the blocks are either $n$-stars or edges. In other words, this refers to decomposing a complete graph into spanning sub-graphs, these spanning sub-graphs are either a union of disjoint $n$-stars or a union of disjoint edges. We will call these $n$-star factors and $1$-factors respectively. A given complete graph which satisfies the necessary condition (\ref{ness}) can potentially be decomposed into $r$ $1$-factors and $s$ $n$-star factors. The goal of this problem is to find a solution for every pair $(r,s)$ and every complete graph that satisfies the necessary conditions. This dissertation focuses on the odd $n$-star cases of the problem. We present the solutions we have found along with the remaining open cases. In Chapter \ref{ch2 WC}, we present a method for decomposing a complete graph into cycles using weighted graphs. This method provides solutions for most cases where $v$ is large. However, this method requires our decomposition to contain a certain number of $1$-factors. Thus, we cannot find solutions for extreme cases, that is $(r,s)$ pairs when $r$ is very small. Because the technique in the Chapter \ref{ch2 WC} does not apply to extreme cases, we began to study the most extreme cases, where $r=1$. In Chapter \ref{ch3 5star}, we give solutions for the case when $r=1$ and $n=5$. The generalized version, when $r=1$ and $n$ is odd, is presented in Chapter \ref{ch4 Nstar}. The results in Chapters \ref{ch3 5star} and \ref{ch4 Nstar} are obtained fundamentally by the same method. However, the constructions in Chapter \ref{ch4 Nstar} are much more complex, and there are many more detailed cases.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy in Mathematical Sciences (PhD)
- Level thesis:degree_level
- Campus Access Dissertation
- Discipline thesis:degree_discipline
- Department of Mathematical Sciences
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Lee, Jehyun
- Committee members dc:contributor.committeemember
-
- William J. Keith
- Robert P. Schneider
- Soner Onder
- Contributors dc:contributor
-
- Melissa S. Keranen
Subjects
dc:subject × 3Identifiers
dc:identifier.*- Identifier
- https://digitalcommons.mtu.edu/etdr/1940