### Abstract

We introduce a sequence d_{n}^{l} (l = 1, 2, . . .) of functions on fraktur G sign_{n} × fraktur G sign_{n}, where fraktur G sign_{n} is the set of all simple, connected, undirected graphs of order n up to isomorphism. We show that when l = 1 or l ≥ n - 1, d_{n}^{l} is a metric on fraktur G sign _{n}. While (fraktur G sign_{n}, d_{n}^{1}) is a totally disconnected metric space that embodies the classical notion of graph isomorphism, (fraktur G sign_{n}, d_{n}^{l}) is a connected metric space whenever l ≥ n - 1. In this paper, we investigate some properties and the relationship between these two spaces. This work was motivated by the problem of virtual path layout in high-speed computer networks, which concerns embedding a specified virtual network into the given physical network in a way that makes optimal use of the physical network resources.

Original language | English (US) |
---|---|

Pages (from-to) | 232-240 |

Number of pages | 9 |

Journal | Aequationes Mathematicae |

Volume | 66 |

Issue number | 3 |

DOIs | |

State | Published - Dec 1 2003 |

### Fingerprint

### Keywords

- Distance between graphs
- Graph embeddings
- Virtual path layout

### ASJC Scopus subject areas

- Mathematics(all)
- Discrete Mathematics and Combinatorics
- Applied Mathematics

### Cite this

*Aequationes Mathematicae*,

*66*(3), 232-240. https://doi.org/10.1007/s00010-003-2687-5