A characterization of the set of all shortest paths in a connected graph
- 1 January 1994
- journal article
- Published by Institute of Mathematics, Czech Academy of Sciences in Mathematica Bohemica
- Vol. 119 (1) , 15-20
- https://doi.org/10.21136/mb.1994.126208
Abstract
Let $G$ be a (finite undirected) connected graph (with no loop or multiple edge). The set $\Cal L$ of all shortest paths in $G$ is defined as the set of all paths $\xi$, then the lenght of $\xi$ does not exceed the length of $\varsigma$. While the definition of $\Cal L$ is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an "almost non-metric" characterization of $\Cal L$: a characterization in which the length of a path greater than one is not considered. Two other theorems are derived from Theorem 1. One of them (Theorem 3) gives a characterization of geodetic graphs.
Keywords
This publication has 0 references indexed in Scilit: