Albion College
Mathematics and Computer Science
Distance-Preserving Graphs
Dennis Ross, `08

Graduate Research Assistant

Computer Science and Engineering

Michigan State University

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.
3:30 PM
All are welcome!
Palenske 227
November 6, 2014