Step Systems on Graphs
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.
Authors
- Manoj Changat (ORCID: https://orcid.org/0000-0001-7257-6031)
- John J. Chavara
- Joseph Mathew
- M. R. Chithra
- Peter F. Stadler (ORCID: https://orcid.org/0000-0002-5016-5191)
Institutions
- University of Vienna (AT)
- Santa Fe Institute (US)
- University of Kerala (IN)
- Government Medical College (IN)
- Universidad Nacional de Colombia (CO)
- Telstra (Australia) (AU)
- Max Planck Institute for Mathematics in the Sciences (DE)
- Economic Research Centre (AZ)
- Leipzig University (DE)
Publication Details
- Journal
- Vietnam Journal of Mathematics
- Published
- 2026-04-21
- DOI
- https://doi.org/10.1007/s10013-026-00808-8
- Primary Topic
- Advanced Algebra and Logic
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- German Academic Exchange Service