Back to search

Marshall University

On 2-primitive triangle decompositions of cocktail party graphs

Abstract

dc:description.abstract

A decomposition of a graph Γ is a collection C of subgraphs, perhaps nonisomorphic, that partition the edges of Γ. Analogously, consider a group of truck drivers whose non-overlapping routes jointly cover all of the roads between a set of cities; that is, each road is traversed by precisely one driver. In this scenario, the cities are the vertices of the graph, the roads are the edges between vertices, and the drivers’ routes are the subgraphs in the decomposition. Given a graph H, we call C an H-decomposition of Γ if each subgraph in C is isomorphic to the graph H. Continuing with the previous analogy, this would imply that each truck driver travels a route which is identical in connectivity between neighboring cities, but differs in locale. A subdecomposition of C refers to a nonempty subset of C which partitions the edges of an induced subgraph of Γ, and C is said to be t-primitive when there exist no proper subdecompositions of C containing t or more subgraphs. To visualize this, we consider a scenario in which t of our truck drivers, along with their respective routes, are infected with an illness that spreads to any healthy driver that travels directly between two sick towns. Assuming that an infected driver will infect their entire route, we ask the natural question of whether this illness spreads to the entire collection of drivers and cities, or whether it ends up confined to some subset of them. If any t sick drivers result in universal infection, the highway network which their routes partition is t-primitive. In this work we examine decompositions of cocktail party graphs into triangles. In particular, we establish the existence of 2-primitive triangle decompositions of cocktail party graphs with 6k + 2 vertices for each nonnegative integer k. Coupled with the results of a recent undergraduate capstone, this work completes the classification of when such decompositions exist for all cocktail party graphs.

Degree

thesis:*
Name thesis:degree_name
Mathematics
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
College of Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Waddell, Ian P.
Contributors dc:contributor
  • Dr. Michael Schroeder, Committee Chairperson
  • Dr. Clayton Brooks
  • Dr. JiYoon Jung

Subjects

dc:subject × 7

Identifiers

dc:identifier.*
Repository record dc:identifier
https://mds.marshall.edu/etd/1759

Chain of custody

source
Harvested from
Marshall University
Base URL
mds.marshall.edu/do/oai/
Last updated
2026-11-21
Source record
OAI-PMH GetRecord
citation

Waddell, Ian P.. On 2-primitive triangle decompositions of cocktail party graphs. Thesis thesis, https://mds.marshall.edu/etd/1759