A metric on the set of connected simple graphs of given order

Kiran R. Bhutani, Bilal Khan

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

We introduce a sequence dnl (l = 1, 2, . . .) of functions on fraktur G signn × fraktur G signn, where fraktur G signn 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, dnl is a metric on fraktur G sign n. While (fraktur G signn, dn1) is a totally disconnected metric space that embodies the classical notion of graph isomorphism, (fraktur G signn, dnl) 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 languageEnglish (US)
Pages (from-to)232-240
Number of pages9
JournalAequationes Mathematicae
Volume66
Issue number3
DOIs
StatePublished - Dec 2003

Keywords

  • Distance between graphs
  • Graph embeddings
  • Virtual path layout

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'A metric on the set of connected simple graphs of given order'. Together they form a unique fingerprint.

Cite this