The toll walk transit function of a graph: axiomatic characterizations and first-order non-definabilityChangat, Manoj (Avtor) Jacob, Jeny (Avtor) Sheela, Lekshmi Kamal K. (Avtor) Peterin, Iztok (Avtor) toll walktransit functionaxiomschordal graphsAT-free graphsPtolemaic graphsdistance-hereditary graphsA 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.20262025-09-24 12:52:38Neznano23680UDK: 519.17ISSN pri članku: 0166-218XDOI: 10.1016/j.dam.2025.09.006COBISS_ID: 250159875sl