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 Date: 11/6/2014 Time: 3:30 PM

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