Characterization of the geodesic distance on infinite graphs

Abstract

Let \(G\) be a connected graph and let \(d_G\) be the geodesic distance on \(V(G)\). The metric spaces \((V(G), d_{G})\) were characterized up to isometry for all finite connected \(G\) by David C. Kay and Gary Chartrand in 1965. The main result of this paper expands this characterization on infinite connected graphs. We also prove that every metric space with integer distances between its points admits an isometric embedding in \((V(G), d_G)\) for suitable \(G\).