2023/10/31 by Changat, Manoj, Jacob, Jeny, Sheela, Lekshmi Kamal K. +1
#05C38 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2310.20237
A walk W=w1w2… wk, k≥ 2, is called a toll walk if w1≠ wk and w2 and wk-1 are the only neighbors of w1 and wk, respectively, on W in a graph G. A toll walk interval T(u,v), u,v∈ 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)× V(G)→ 2V(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.