# zbMATH — the first resource for mathematics

A characterization of the set of all shortest paths in a connected graph. (English) Zbl 0807.05045
Let $$G= (V,E)$$ be a simple connected graph with $$| V|\geq 2$$. The set $$\mathcal S$$ of all shortest paths in $$G$$ is the set of all paths in $$G$$ such that if $$\xi\in {\mathcal S}$$ and $$\eta$$ is any path in $$G$$ with the same endpoints as $$\xi$$, then $$\text{length }\xi\leq \text{length }\eta$$. The author presents a set of axioms that “almost” dispenses with the concept of length in characterizing $$\mathcal S$$. A simpler set of axioms characterizes $$\mathcal S$$ in the case when $$G$$ is bipartite.

##### MSC:
 05C38 Paths and cycles 05C75 Structural characterization of families of graphs 05C12 Distance in graphs
##### Keywords:
geodetic graphs; connected graph; shortest paths
Full Text: