20.500.12556/DiRROS-23680 The toll walk transit function of a graph: axiomatic characterizations and first-order non-definability A walk $W=w_1w_2\dots w_k$, $k\geq 2$, is called a toll walk if $w_1\neq w_k$ and $w_2(w_{k-1})$ are the only neighbors of $w_1(w_k)$ on $W$ in a graph $G$. A toll walk interval $T(u,v)$, $u,v\in V(G)$, contains all the vertices that belong to a toll walk between $u$ and $v$. The toll walk intervals yield a toll walk transit function $T:V(G)\times V(G)\rightarrow 2^{V(G)}$. We represent several axioms that characterize the toll walk transit function among chordal graphs, trees, asteroidal triple-free graphs, Ptolemaic graphs, and distance hereditary graphs. We also show that the toll walk transit function can not be described in the language of first-order logic for an arbitrary graph. toll walk transit function axioms chordal graphs AT-free graphs Ptolemaic graphs distance-hereditary graphs sprehod s cestninjnjem tranzitna funkcija aksiomi tetivni grafi grafi brez asteroidnih trojk Ptolemaični grafi razdaljno dedni grafi true false true Angleški jezik Slovenski jezik Neznano 2025-09-24 12:52:38 2025-09-24 12:52:39 2025-10-24 03:54:49 0000-00-00 00:00:00 2026 0 0 str. 128-145 Vol. 380 Feb. 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2026-02-01 519.17 0166-218X 10.1016/j.dam.2025.09.006 250159875 1-s2.0-S0166218X25005347-main.pdf 1-s2.0-S0166218X25005347-main.pdf 1 C850B80BDF02DCD542CA1AC9B73946C7 9d9cc672a74503c20eccb26aa09ac0f9807dc76a1a1db7138a14c1fe64a2bf94 3b573f53-9937-11f0-9bb7-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=35079 https://www.sciencedirect.com/science/article/pii/S0166218X25005347 1 975e4f1a-9934-11f0-9bb7-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=35078 Inštitut za matematiko, fiziko in mehaniko 0 0 0