Albion College

Mathematics and Computer Science

Mathematics and Computer Science

COLLOQUIUM

Distance-Preserving Graphs

Dennis Ross, `08

Graphs provide terrific models, and some powerful mathematical machinery, to better understand many practical and theoretical problems. One important relationship between vertices of a graph is the length of the shortest path connecting them. We will explore a class of problems which seek to fix this distance between vertices while reducing the order of the graph.
Consider a simple graph $G$ of order $n$. We say $G$ is distance-preserving if, for all integers $k$ such that $1 < k < n$,
there exists an order $k$ induced subgraph of $G$ where $d_G(x,y)=d_H(x,y)$ for all pairs of $x,y\in H$. We will explore the definitions and properties of distance-hereditary graphs, distance-preserving graphs, and distance-preserving trees. We will then continue with an extremal proof on the constructability of regular distance-preserving graphs. Additionally, we will discuss some open problems and see some practical applications.