Combinatorics and Graph Theory

•  Emad Zahedi, MSU
•  On Distance Preserving and Sequentially Distance Preserving Graphs
•  02/28/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
619 Red Cedar Road
C212 Wells Hall
East Lansing, MI 48824

Phone: (517) 353-0844
Fax: (517) 432-1562

College of Natural Science