Albion College Mathematics and Computer Science Colloquium

Title: Distance-Preserving Graphs
Speaker:Dennis Ross, `08
Graduate Research Assistant
Computer Science and Engineering
Michigan State University
East Lansing, MI
Abstract: 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.
Location: Palenske 227
Time: 3:30 PM

author  = "{Dennis Ross, `08}",
title   = "{Distance-Preserving Graphs}",
address = "{Albion College Mathematics and Computer Science Colloquium}",
month   = "{6 November}",
year    = "{2014}"