Characterizing All Graphs With At Most Four Boundary Vertices

What does it mean for graphs to have boundaries? Recall that the boundary of subsets in $\mathbb{R}^n$ is induced by a metric. Graphs also have a metric, and thus one may try to find a subset of vertices in a graph which may behave like a "boundary" to the graph. Steinerberger proposed a notion of a boundary for graphs which also establishes a corresponding isoperimetric inequality: larger graphs should have more boundary vertices. For our research, we characterized all graphs with two, three, or four boundary vertices. We characterize all graphs with three boundary vertices as belonging to one of two infinite families of graphs. We also characterize all graphs with four boundary vertices as belonging to one of eight families of graphs, five of the families being infinite. Our work parallels previous work done by Hasegawa and Saito, as well as Müller, Pór, and Sereni for a different notion of graph boundaries defined by Chartrand, Erwin, Johns, and Zhang. This project was done under WXML, a math research lab at the University of Washington, under Dr. Steinerberger and Kevin Liu.