The Weak-Toll Function of a Graph: Axiomatic Characterizations and First-Order Non-definability

Toll walks on connected graphs are introduced to characterize dominating pairs of vertices in interval graphs. A weak-toll walk is an immediate generalization of a toll walk in a graph. The set of all vertices lying on weak-toll walks between two given vertices gives rise to the notion of the weak-toll function, denoted \(W_T\) , of a connected graph. In this paper, we characterize the weak-toll function of trees, chordal graphs, and unit interval graphs. This, in turn, provides an additional characterization of trees and unit interval graphs using a set of first-order axioms defined on an arbitrary function, known as the transit function, which is defined for every pair of elements in a non-empty finite set. Furthermore, we prove that an axiomatic characterization of the function \(W_T\) of an arbitrary connected graph is impossible using a set of first-order axioms.