The induced path function, monotonicity and betweenness Original Research Article

The geodesic interval function image of a connected graph allows an axiomatic characterization involving axioms on the function only, without any reference to distance, as was shown by Nebeský . Surprisingly, Nebeský showed that, if no further restrictions are imposed, the induced path function image of a connected graph image does not allow such an axiomatic characterization. Here image consists of the set of vertices lying on the induced paths between image and image. 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 image. The function image satisfies betweenness if image, with image, implies image and image implies image. It is monotone if image implies image. In the case where we restrict ourselves to functions image that satisfy betweenness, or monotonicity, we are able to provide such axiomatic characterizations of image by transit axioms only. The graphs involved can all be characterized by forbidden subgraphs.