Abstract
dc:descriptionLet 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.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Nussbaum, Ronald
- Contributors dc:contributor
-
- Esfahanian, Abdol-Hossein
- Tan, Pang-Ning
- Torng, Eric
- Goodman, Erik
Subjects
dc:subject × 3Rights
dc:rights- Statement dc:rights
-
- In Copyright
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
-
etd:2936
isbn:9781321440102
isbn:1321440103
oclc:973326806
umi:3668738
local:Nussbaum_grad.msu_0128D_13466 - OAI record oai:identifier
- https://d.lib.msu.edu/oai?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Ad.lib.msu.edu%3Aetd_2936