Back to search

Michigan State University

Distance-preserving graphs

Abstract

dc:description

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.

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 × 3

Rights

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

Chain of custody

source
Harvested from
Michigan State University
Base URL
d.lib.msu.edu/oai
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Nussbaum, Ronald. Distance-preserving graphs. 2014. https://doi.org/doi:10.25335/fenx-8163