The induced path function, monotonicity and betweenness
The geodesic interval function I 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 J of a connected graph G G does not allow such an axiomatic characterization. Here J(u,v) J ( u , v ) consists of the set of vertices lying on the induced paths between u u and v 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 J . The function J J satisfies betweenness if w?J(u,v) w ? J ( u , v ) , with w?u w ? u , implies u?J(w,v) u ? J ( w , v ) and x?J(u,v) x ? J ( u , v ) implies J(u,x)?J(u,v) J ( u , x ) ? J ( u , v ) . It is monotone if x,y?J(u,v) x , y ? J ( u , v ) implies J(x,y)?J(u,v) J ( x , y ) ? J ( u , v ) . In the case where we restrict ourselves to functions J J that satisfy betweenness, or monotonicity, we are able to provide such axiomatic characterizations of J J by transit axioms only. The graphs involved can all be characterized by forbidden subgraphs.
induced path monotone betweenness transit function long cycle house domino p p -graph p p p p p