Digital metrics: A graph-theoretical approach

Abstract

Consider the following two graphs M and N, both with vertex set Z x Z, where Z is the set of all integers. In M, two vertices are adjacent when their euclidean distance is 1, while in N, adjacency is obtained when the distance is either 1 or [radical sign]2. By definition, H is a metric subgraph of the graph G if the distance between any two points of H is the same as their distance in G. We determine all the metric subgraphs of M and N. The graph-theoretical distances in M and N are equal respectively to the city block and chessboard matrics used in pattern recognition.