Date of Award

2023

Degree Name

Mathematics

College

College of Science

Type of Degree

M.A.

Document Type

Thesis

First Advisor

Dr. Michael Schroeder, Committee Chairperson

Second Advisor

Dr. Clayton Brooks

Third Advisor

Dr. JiYoon Jung

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.

Subject(s)

Graph theory – Mathematics.

Decomposition (Mathematics).

Download

Share

COinS