On distance preserving and sequentially distance preserving graphs

Smith, JP ORCID: https://orcid.org/0000-0002-4209-1604 and Zahedi, E, 2025. On distance preserving and sequentially distance preserving graphs. The Art of Discrete and Applied Mathematics. ISSN 2590-9770

Preview

Text 2378021_Smith.pdf - Post-print Download (407kB) | Preview

Abstract

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.

Item Type:	Journal article
Publication Title:	The Art of Discrete and Applied Mathematics
Creators:	Smith, J.P. and Zahedi, E.
Publisher:	University of Primorska Press
Date:	14 February 2025
ISSN:	2590-9770
Identifiers:	Number Type 10.26493/2590-9770.1813.5ce DOI 2378021 Other
Rights:	This work is licensed under https://creativecommons.org/licenses/by/4.0/
Divisions:	Schools > School of Science and Technology
Record created by:	Jonathan Gallacher
Date Added:	18 Feb 2025 09:24
Last Modified:	18 Feb 2025 09:24
URI:	https://irep.ntu.ac.uk/id/eprint/53057

Actions (login required)

Edit View

Statistics

Views

Downloads