On Distance Preserving and Sequentially Distance Preserving Graphs

A graph \(H\) is an \emph{isometric} subgraph of \(G\) if \(d_H(u,v)= d_G(u,v)\), for every pair~\(u,v\in V(H)\). A graph is \emph{distance preserving} if it has an isometric subgraph of every possible order. A graph is \emph{sequentially distance preserving} if its vertices can be ordered such that...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-01
Main Authors: Smith, Jason P, Zahedi, Emad
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A graph \(H\) is an \emph{isometric} subgraph of \(G\) if \(d_H(u,v)= d_G(u,v)\), for every pair~\(u,v\in V(H)\). A graph is \emph{distance preserving} if it has an isometric subgraph of every possible order. A graph is \emph{sequentially distance preserving} if its vertices can be ordered such that deleting the first \(i\) vertices results in an isometric subgraph, for all \(i\ge1\). 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.
ISSN:2331-8422