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.


05C38 Paths and cycles
05C75 Structural characterization of families of graphs
05C12 Distance in graphs
Full Text: EuDML