Back to search

Michigan Technological University

On graph decompositions: Exploring the stars and stripes problem with odd n-stars

Abstract

dc:description.abstract

This 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 × 3

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Michigan Technological University
Base URL
digitalcommons.mtu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lee, Jehyun. On graph decompositions: Exploring the stars and stripes problem with odd n-stars. Campus Access Dissertation thesis, https://doi.org/10.37099/mtu.dc.etdr/1940