pith. sign in

arxiv: 1507.03615 · v1 · pith:ET6HUYRZnew · submitted 2015-07-13 · 🧮 math.CO

Distance Preserving Graphs

classification 🧮 math.CO
keywords graphgraphsconditiondistanceeveryimpliesisometricorder
0
0 comments X
read the original abstract

Given a graph $G$ then a subgraph $H$ is $isometric$ if, for every pair of vertices $u,v$ of $H$, we have $d_H(u,v) = d_G(u,v)$. We say a graph $G$ is $distance\ preserving\ (dp)$ if it has an isometric subgraph of every possible order up to the order of $G$. 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. We also find a condition on the girth of $G$ which implies that it is not dp. In closing, we discuss other work and open problems concerning dp graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.