A graph H is an isometric subgraph of G if d_H(u,v)=d_G(u,v), for every pair u,v ? V(H). A graph is distance preserving if it has an isometric subgraph of every possible order. A graph is sequentially distance preserving if its vertices can be ordered such that deleting the first i vertices results in an isometric subgraph, for all i?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 sequentially distance preserving and thus distance preserving. Next we consider the distance preserving property on graphs with a cut vertex. Finally, we define a family of non-distance preserving graphs constructed from cycles.

Rights

URN

URN:NBN:SI:DOC-H48D12J0

COBISSID

285852163

DOI

10.26493/2590-9770.1813.5ce

Added

08.09.2026

Metadata

Citation

APA:

Smith, Jason P., Zahedi, Emad (2025). On distance preserving and sequentially distance preserving graphs. The art of discrete and applied mathematics, volume 8, issue 2, article p2.05, str. 1-10. URN:NBN:SI:DOC-H48D12J0 from http://www.dlib.si

MLA:

Smith, Jason P., Zahedi, Emad. "On distance preserving and sequentially distance preserving graphs." The art of discrete and applied mathematics volume 8. issue 2. article p2.05 (2025) str. 1-10.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-H48D12J0>