Geodetic metrizations of graphs (Q1297490)

A graph can be metrized by assigning a length to each of its edges. Such a graph is said to be geodetic if for each pair of vertices there is a unique geodesic joining them. The paper starts with proofs that every graph can be metrized in such a way that there are unique geodesics, each of which is a geodesic in the usual metrization with unit edge lengths (these graphs are said to be normally geodetic). Geodetic metrizations of the four- and eight-connection graphs of the digital plane which can be processed easily on a computer are investigated. Examples are given of normally geodetic integral metrizations of arbitrarily large rectangular blocks of these planes. However, it is proved that there are no normally geodetic metrizations of the whole of these planes which are periodic in each variable.