zbMATH — the first resource for mathematics

Route systems of a connected graph. (English) Zbl 0820.05021
For a graph \(G\), a route system is a set of paths satisfying five axioms, which generalise some properties of the set \({\mathcal S} (G)\) of all shortest paths of \(G\). Continuing his previous work (see [Czech. Math. J. 41(116), No. 2, 260-264 (1991; Zbl 0765.05060)] and [Math. Bohem. 119, No. 1, 15-20 (1994; Zbl 0807.05045)]), the author establishes some properties concerning route systems, in particular those minimal or maximal with respect to set theoretical inclusion among all route systems. He shows that (i) a route system \({\mathcal K}\) is minimal if and only if it satisfies a further axiom; (ii) if \(G\) is geodetic then \({\mathcal S} (G)\) is not maximal, unless \(G\) is a tree; (iii) if \(G\) is bipartite then \({\mathcal S} (G)\) is maximal. It is conjectured that the converse of (iii) is true.

05C12 Distance in graphs
05C38 Paths and cycles
Full Text: EuDML