Distance-preserving graphs Nussbaum, Ronald Graph theory Isometric projection Data structures (Computer science) Computer science Thesis Ph. D. Michigan State University. Computer Science 2014. Let G be a simple graph on n vertices, where d_G(u,v) denotes the distance between vertices u and v in G. An induced subgraph H of G is isometric if d_H(u,v)=d_G(u,v) for all u,v in V(H). We say that G is a distance-preserving graph if G contains at least one isometric subgraph of order k for every k where 1<=k<=n.A number of sufficient conditions exist for a graph to be distance-preserving. We show that all hypercubes and graphs with delta(G)>=2n/3-1 are distance-preserving. Towards this end, we carefully examine the role of "forbidden" subgraphs. We discuss our observations, and provide some conjectures which we computationally verified for small values of n. We say that a distance-preserving graph is sequentially distance-preserving if each subgraph in the set of isometric subgraphs is a superset of the previous one, and consider this special case as well.There are a number of questions involving the construction of distance-preserving graphs. We show that it is always possible to add an edge to a non-complete sequentially distance-preserving graph such that the augmented graph is still sequentially distance-preserving. We further conjecture that the same is true of all distance-preserving graphs. We discuss our observations on making non-distance-preserving graphs into distance preserving ones via adding edges. We show methods for constructing regular distance-preserving graphs, and consider constructing distance-preserving graphs for arbitrary degree sequences. As before, all conjectures here have been computationally verified for small values of n. Includes bibliographical references. Description based on online resource; title from PDF t.p. (viewed on Oct. 18, 2017) Esfahanian, Abdol-Hossein Tan, Pang-Ning Torng, Eric Goodman, Erik 2014 text Electronic dissertations Academic theses application/pdf 1 online resource (x, 81 pages) : illustrations etd:2936 isbn:9781321440102 isbn:1321440103 umi:3668738 local:Nussbaum_grad.msu_0128D_13466 https://doi.org/doi:10.25335/M5RM50 eng In Copyright