Abstract Step systems of connected graphs were introduced by Ladislav Nebeský as a means of describing shortest paths solely in terms of local information. A ternary relation T encodes, for each point u , the first step x towards a target v . Eight first-order axioms characterize the ternary relation T that are step systems. Here we show that one of Nebeský’s eight axioms is in fact redundant. Moreover, we characterize the step systems of bipartite graphs, partial cubes, and weakly modular graphs in terms of first-order axioms. In each case we show that the corresponding sets of axioms are non-redundant.
Changat et al. (Tue,) studied this question.