The induced path function, monotonicity and betweenness

The geodesic interval function I of a connected graph allows an axiomatic characterization involving axioms on the function only, without any reference to distance, as was shown by Nebeský [20]. Surprisingly, Nebeský [23] showed that, if no further restrictions are imposed, the induced path function J of a connected graph G does not allow such an axiomatic characterization. Here J(u,v) consists of the set of vertices lying on the induced paths between u and v. This function is a special instance of a transit function. In this paper we address the question what kind of restrictions could be imposed to obtain axiomatic characterizations of J. The function J satisfies betweenness if wset membership, variantJ(u,v), with w≠u, implies unegated set membershipJ(w,v) and xset membership, variantJ(u,v) implies J(u,x)subset of or equal toJ(u,v). It is monotone if x,yset membership, variantJ(u,v) implies J(x,y)subset of or equal toJ(u,v). In the case where we restrict ourselves to functions J that satisfy betweenness, or monotonicity, we are able to provide such axiomatic characterizations of J by transit axioms only. The graphs involved can all be characterized by forbidden subgraphs.

• View at Publisher
• View at Scopus
• View at Web of Science