The induced path function, monotonicity and betweenness
Discrete Applied Mathematics , Volume 158 - Issue 5 p. 426- 433
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ý . Surprisingly, Nebeský  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.
|Betweenness, Domino, House, Induced path, Long cycle, Monotone, P-graph, Transit function|
|Econometric Institute Reprint Series|
|Discrete Applied Mathematics|
|Organisation||Erasmus School of Economics|
Changat, M, Mathew, J, & Mulder, H.M. (2010). The induced path function, monotonicity and betweenness. Discrete Applied Mathematics, 158(5), 426–433. doi:10.1016/j.dam.2009.10.004