A characterization of the set of all shortest paths in a connected graph. (English) Zbl 0807.05045

Nebeský, Ladislav

Math. Bohem. 119, No. 1, 15-20 (1994).

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.

Reviewer: N.F.Quimpo (Manila)

MSC:

05C38	Paths and cycles
05C75	Structural characterization of families of graphs
05C12	Distance in graphs

Keywords:

geodetic graphs; connected graph; shortest paths