Resumen de A metric on the set of connected simple graphs of given order
Kiran R. Bhutani, Bilal Khan
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.
