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ý . 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.
|Keywords||Betweenness, Domino, House, Induced path, Long cycle, Monotone, P-graph, Transit function|
|Persistent URL||dx.doi.org/10.1016/j.dam.2009.10.004, hdl.handle.net/1765/18216|
|Series||Econometric Institute Reprint Series|
|Journal||Discrete Applied Mathematics|
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