×

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
PDF BibTeX XML Cite
Full Text: EuDML