## Combinatorics and Graph Theory

•  On Distance Preserving and Sequentially Distance Preserving Graphs
•  02/21/2017
•  4:10 PM - 5:00 PM
•  C304 Wells Hall

A graph H is an isometric subgraph of G if d_H(u,v) = d_G(u,v), for every pair u,v in V(H), where d denotes distance. A graph is distance preserving (dp) if it has an isometric subgraph of every possible order. We consider how to add a vertex to a dp graph so that the result is a dp graph. This condition implies that chordal graphs are dp. A graph is sequentially distance preserving (sdp) if its vertices can be ordered such that deleting the first i vertices results in an isometric subgraph, for all i at least 1. We give an equivalent condition to sequentially distance preserving based upon simplicial orderings. Using this condition, we prove that if a graph does not contain any induced cycles of length 5 or greater, then it is sdp. In closing, we discuss our results, other work and open problems concerning dp graphs.

## Contact

Department of Mathematics
Michigan State University