The induced path function, monotonicity and betweenness

https://doi.org/10.1016/j.dam.2009.10.004Get rights and content
Under an Elsevier user license
open archive

Abstract

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 wJ(u,v), with wu, implies uJ(w,v) and xJ(u,v) implies J(u,x)J(u,v). It is monotone if x,yJ(u,v) implies J(x,y)J(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

Transit function
Induced path
Betweenness
Monotone
Long cycle
House
Domino
P-graph

Cited by (0)