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

• Autores: Kiran R. Bhutani, Bilal Khan
• Localización: Aequationes mathematicae, ISSN 0001-9054, Vol. 66, Nº. 3, 2003, págs. 232-240
• Idioma: inglés
• DOI: 10.1007/s00010-003-2687-5
• Texto completo no disponible (Saber más ...)
• Resumen

  • We introduce a sequence $ d{^\ell_n} (\ell = 1, 2, \ldots) $ of functions on $ {\mathcal G}{_n} \times {\mathcal G}{_n} $, where $ {\mathcal G}_n $ is the set of all simple, connected, undirected graphs of order n up to isomorphism. We show that when $ \ell = 1 $ or $ \ell \geq n-1 $, $ d{^\ell_n} $ is a metric on $ {\mathcal G}_n $. While $ ({\mathcal G}{_n}, d{^1_n}) $ is a totally disconnected metric space that embodies the classical notion of graph isomorphism, $ ({\mathcal G}{_n}, d{^\ell_n}) $ is a connected metric space whenever $ \ell \geq 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.