Scholarlink

<p>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 <i>T</i> encodes, for each point <i>u</i>, the first step <i>x</i> towards a target <i>v</i>. Eight first-order axioms characterize the ternary relation <i>T</i> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Step Systems on Graphs

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年4月21日

查看全文
  • Manoj Changat,
  • John J. Chavara,
  • M. R. Chithra,
  • Joseph Mathew,
  • Peter F. Stadler

摘要

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.