Distancepreserving graphs
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 distancepreserving 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 distancepreserving. We show that all hypercubes and graphs with delta(G)>=2n/31 are distancepreserving. 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 distancepreserving graph is sequentially distancepreserving 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 distancepreserving graphs. We show that it is always possible to add an edge to a noncomplete sequentially distancepreserving graph such that the augmented graph is still sequentially distancepreserving. We further conjecture that the same is true of all distancepreserving graphs. We discuss our observations on making nondistancepreserving graphs into distance preserving ones via adding edges. We show methods for constructing regular distancepreserving graphs, and consider constructing distancepreserving graphs for arbitrary degree sequences. As before, all conjectures here have been computationally verified for small values of n.
Read
 In Collections

Electronic Theses & Dissertations
 Copyright Status
 In Copyright
 Material Type

Theses
 Authors

Nussbaum, Ronald
 Thesis Advisors

Esfahanian, AbdolHossein
 Committee Members

Tan, PangNing
Torng, Eric
Goodman, Erik
 Date
 2014
 Program of Study

Computer Science  Doctor of Philosophy
 Degree Level

Doctoral
 Language

English
 Pages
 x, 81 pages
 ISBN

9781321440102
1321440103
 Permalink
 https://doi.org/doi:10.25335/M5RM50