Author ORCID Identifier
Date Available
3-5-2020
Year of Publication
2020
Document Type
Doctoral Dissertation
Degree Name
Doctor of Philosophy (PhD)
College
Arts and Sciences
Department/School/Program
Mathematics
Advisor
Dr. Benjamin Braun
Abstract
A graph property is monotone if it is closed under the removal of edges and vertices. Given a graph G and a monotone graph property P, one can associate to the pair (G,P) a simplicial complex, which serves as a way to encode graph properties within faces of a topological space. We study these graph-theoretic simplicial complexes using combinatorial and topological approaches as a way to inform our understanding of the graphs and their properties.
In this dissertation, we study two families of simplicial complexes: (1) neighborhood complexes and (2) k-matching complexes. A neighborhood complex is a simplicial complex of a graph with vertex set the vertices of the graph and facets given by neighborhoods of each vertex of the graph. In 1978, Lov\'asz used neighborhood complexes as a tool for studying lower bounds for the chromatic number of graphs. In Chapter 2, we will prove results about the connectivity of neighborhood complexes in relation to Haj\'os-type constructions and analyze randomly generated graphs arising from two Haj\'os-type stochastic algorithms using SageMath. Chapter 3 will focus on k-matching complexes. A k-matching complex of a graph is a simplicial complex with vertex set given by edges of the graph and faces given sets of edges in the graph such that each vertex of the induced graph has degree at most k. We pursue the study of k-matching complexes and investigate 2-matching complexes of wheel graphs and caterpillar graphs.
Digital Object Identifier (DOI)
https://doi.org/10.13023/etd.2020.254
Recommended Citation
Vega, Julianne, "Graph-Theoretic Simplicial Complexes, Hajos-type Constructions, and k-Matchings" (2020). Theses and Dissertations--Mathematics. 74.
https://uknowledge.uky.edu/math_etds/74
