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:DennisRoss`08:2014:11:6, author = "{Dennis Ross, `08}", title = "{Distance-Preserving Graphs}", address = "{Albion College Mathematics and Computer Science Colloquium}", month = "{6 November}", year = "{2014}" }