Distance-preserving graphs
Nussbaum, Ronald
author
Esfahanian, Abdol-Hossein
thesis advisor
Tan, Pang-Ning
degree committee member
Torng, Eric
degree committee member
Goodman, Erik
degree committee member
text
Text
Theses
No place, unknown, or undetermined
2014
2014
eng
English
application/pdf
x, 81 pages
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.
by Ronald Nussbaum
Thesis (Ph. D.)--Michigan State University. Computer Science, 2014
Includes bibliographical references
Graph theory
Isometric projection
Data structures (Computer science)
Data structures (Computer science)
Graph theory
Isometric projection
Computer science
Electronic Theses & Dissertations
etd_root
9781321440102
1321440103
973326806
3668738
Nussbaum_grad.msu_0128D_13466
In Copyright
This item is protected by copyright and/or related rights. You are free to use this item in any way that is permitted by the copyright and related rights legislation that applies to your use. For more information about U.S. copyright law and fair use, see <a href="http://www.lib.msu.edu/copyright/">http://www.lib.msu.edu/copyright</a>
https://doi.org/doi:10.25335/M5RM50
aacr
MiEM
Michigan State University. Libraries
2018-04-30
2021-03-24
973326806
Converted from MARCXML to MODS version 3.7 using a custom XSLT.
eng