Geodetic metrizations of graphs
type: Item
instance of: scholarly article
title: Geodetic metrizations of graphs
zbMATH Open document ID: 0924.05020
DOI: 10.1016/S0012-365X(98)00153-8
author: Frank Rhodes
author: Robert A. Melter
published in: Discrete Mathematics
publication date: 1999-11-03T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1321852
zbMATH Keywords: geodetic graph
zbMATH Keywords: digital plane
zbMATH Keywords: four-connection graph
zbMATH Keywords: eight-connection graph
zbMATH Keywords: normally geodetic metrization
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: Q4692391
full work available at URL: s0012-365x(98)00153-8
OpenAlex ID: W2063758418
Recommended article: Q3767372
Recommended article: A characterization of geodetic graphs
Recommended article: Q6175870
Recommended article: Geodetic Sets in Graphs
Recommended article: Geodetic sets in graphs
Recommended article: An algebraic characterization of geodetic graphs
Recommended article: Geodesic geometry on graphs
Recommended article: Q4537191
Recommended article: On uniformly geodetic graphs
Recommended article: Geodetic convexity and Kneser graphs
description: scientific article; zbMATH DE number 1321852