Discrete Mathematics and Combinatorics Commons^™

Structure Of Extremal Unit Distance Graphs, Kaylee Weatherspoon

Senior Theses

This thesis begins with a selective overview of problems in geometric graph theory, a rapidly evolving subfield of discrete mathematics. We then narrow our focus to the study of unit-distance graphs, Euclidean coloring problems, rigidity theory and the interplay among these topics. After expounding on the limitations we face when attempting to characterize finite, separable edge-maximal unit-distance graphs, we engage an interesting Diophantine problem arising in this endeavor. Finally, we present a novel subclass of finite, separable edge-maximal unit distance graphs obtained as part of the author's undergraduate research experience.