Author ORCID Identifier

https://orcid.org/0000-0002-9904-9677

Date Available

3-5-2020

Year of Publication

2020

Degree Name

Doctor of Philosophy (PhD)

Document Type

Doctoral Dissertation

College

Arts and Sciences

Department/School/Program

Mathematics

First 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

Share

COinS