๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Geodetic metrizations of graphs

โœ Scribed by Frank Rhodes; Robert A. Melter

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
665 KB
Volume
194
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

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. It is said to be normally geodetic if each of these unique geodesics is one of the geodesics in the usual metrization of the graph in which each edge is given unit length. It is shown that every graph admits a normally geodetic metrization.

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. @

๐Ÿ“œ SIMILAR VOLUMES

On F-geodetic graphs
On F-geodetic graphs
โœ Raffaele Scapellato ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 868 KB

We study the graphs in which the number of geodesics between any two vertices depends only on their distance. We consider also a connection between some of these graphs and geodetic graphs.

Geodetic graphs of diameter two
Geodetic graphs of diameter two
โœ A. Blokhuis; A. E. Brouwer ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› Springer ๐ŸŒ English โš– 365 KB

We survey what is known on geodetic graphs of diameter two and discuss the implications of a new strong necessary condition for the existence of such graphs.

The geodetic number of a graph
The geodetic number of a graph
โœ Frank Harary; Emmanuel Loukakis; Constantine Tsouros ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 406 KB
The recognition of geodetically connecte
The recognition of geodetically connected graphs
โœ Jou-Ming Chang; Chin-Wen Ho ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 849 KB

Let G = ( y E) be a graph with vertex set V of size n and edge set E of size m. A vertex LJ E V is called a hinge vertex if the distance of any two vertices becomes longer after u is removed. A graph without hinge vertex is called a hinge-free graph. In general, a graph G is k-geodetically connected

Minimum 3-geodetically connected graphs
Minimum 3-geodetically connected graphs
โœ Martina Bosฤฑฬkovรก ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 793 KB

A graph G is k-geodetically connected (k-GC) if it is connected and the removal of at least k vertices is required to increase the distance between at least one pair of vertices or reduce G to a single vertex. We completely characterize the class of minimum 3-GC graphs that have the fewest edges for