Characterization of the geodesic distance on infinite graphs

Abstract

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