Loading...
Please wait, while we are loading the content...
Similar Documents
C O ] 7 M ay 2 01 4 On Constructing Regular Distance-Preserving Graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ross, Dennis Sagan, Bruce E. Nussbaum, Ronald Esfahanian, Abdol-Hossein |
| Copyright Year | 2014 |
| Abstract | Let G be a simple, connected graph on n vertices. LetdG(u, v) denote the distance between vertices u andv in G. A subgraphH of G is isometric if dH(u, v) = dG(u, v) for everyu, v ∈ V (H). We say that G is adistancepreserving graphif G contains at least one isometric subgraph of order k for everyk, 1 ≤ k ≤ n. In this paper we construct regular distance-preserving graphs of all possible orders and degrees of regularity. By m odifying the Havel-Hakimi algorithm, we are able to construct distance p reserving graphs for certain other degree sequences as well. We include a disc ussion of some related conjectures which we have computationally verified for small values of n. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://arxiv.org/pdf/1405.1713v1.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
