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