- On Distance Preserving and Sequentially Distance Preserving Graphs
- 02/28/2017
- 4:10 PM - 5:00 PM
- C304 Wells Hall
- Emad Zahedi, MSU
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.