Betweenness in graphs: A short survey on shortest and induced path betweenness

Peer review under responsibility of Kalasalingam University.

This work was supported by NBHM DAE under file NBHM/2/48(9)/2014/NBHM (R.P.)/R&D-II/4364.

Abstract

Betweenness is a universal notion present in several disciplines of mathematics. The notion of betweenness has a profound history and many pioneers like Euclid, Pasch, Hilbert have studied betweenness axiomatically. In discrete mathematics too, betweenness is present and several authors have worked on this concept from an axiomatic view. In graph theory, betweenness is developed mainly as metric betweenness, studied using the shortest path metric in a connected graph, thus resulting in the notion of the interval function. Many interesting results are available in graph theory using the interval function. The interval function is generalized to induced path function by replacing shortest paths by induced paths. The induced path betweenness also captured attention among graph theorists with several interesting results to date. From an axiomatic point of view, two pertinent questions can be framed on these functions. Is it possible to axiomatically characterize the interval function of some special graphs using some set of first order axioms defined on an arbitrary transit function? Is it possible to characterize the graphs with the help of their interval functions? In this paper, we survey the results as answers to these questions available from the research papers.

Keywords:

• Betweenness
• Interval function
• Induced path function

1 Introduction

The experience of “Betweenness” is natural in our everyday life. Betweenness is an ontological entity, only when there are two points either in space or time. This is true in one’s own life and in one’s relationship with others. In this sense, betweenness is a universal concept, but at the same time knowledge about it warrants historical ontology.

In Mathematics too, betweenness is a natural concept which is present in several branches like Geometry, Algebra, Poset Theory, Metric Geometry, Graph Theory and in many other structures. For example, in Geometry a point $x$ is between two other points, say $a$ and $b$, if $x$ lies in a line segment between $a$ and $b$; $a\le x\le b$ in a poset $(X,\le )$; $d(a,x)+d(x,b)=d(a,b)$, in a metric space $(X,d)$. Betweenness can be studied axiomatically by defining independent axioms on a non-empty set.

Betweenness as a concept was first formulated in Geometry. This concept has genealogical antecedence from the geometry of Euclid. However, early $20$th century mathematicians recognized that Euclid’s system of axioms was incomplete. Concepts such as “between”, “inside” and “outside” were not precise. Nevertheless pictures were used for reasoning by Euclid. In 1882, Moritz Pasch, one of the pioneering geometer, carefully examined these missing unstated assumptions and played a crucial role in the development of the axiomatic method in Geometry. The explicit axiomatization of the notion of betweenness was first carried out by Pasch in [1]. Also refer [2,3]. This has provided a solid foundation (in the spirit of synthetic geometry) for bounded convex domains inside the projective spaces. The deductivist nature of Pasch’s geometry opened a new era in the axiomatic foundation of geometry.

The notion of betweenness does not appear intrinsically in the book by Pasch as he speaks of a point $C$ belonging to segment $AB$.

Pasch in the same book axiomatized a closed line quaternary relation of separation $∕∕$ with $ab∕∕cd$ is termed as the point-pair $(a,b)$ separates the point-pair $(c,d)$. Pasch axiom of order, establishes a betweenness relation for points on a line as well as the property that a line intersecting one side of the triangle must necessarily intersect another side. Instead of the undefined primitive terms, like the point, line, and plane by Euclid, Pasch introduced the point, the line segment and the planar-segment as the basic notions, in terms of which the line and the plane are defined. Followed by Pasch, Peano gradually refined the axioms of betweenness in geometry [4].

David Hilbert developed the modern system of axioms, which removed these limitations, in his book “Grundlagen der Geometrie” (Foundations of Geometry); which was first published in the year 1899, see [5]. The undefined terms (according to Hilbert) are points, lines, planes, “to be on”, “to be between” and “to be congruent”. The axioms of geometry, which implicitly describe the undefined terms, are grouped into five of which the second set of axioms are the axioms of betweenness. What is being axiomatized in this group of axioms is the relation $\mathcal{B}$ which, intuitively speaking, says whether a point is between two other points or not. Intuitively, we may think of $\mathcal{B}(A,B,C)$ as the point $B$ is between points $A$ and $C$.

Marlow Sholander developed a theory of betweenness using ternary relations to study lattices, trees and semi-lattices; in particular, he introduced what is a median semi-lattice using his theory of betweenness. He published two papers. In his first paper titled “Trees, lattices, order and betweenness” see [6], he investigates betweenness for various kinds of orderings. This paper considers postulates expressed in terms of “segments”, “medians”, and “betweenness”; and characterizations are obtained for trees, lattices, and partially ordered sets. In the second paper, it is shown that lattices and trees have a common generalization, which he calls ‘median semi lattice’, see [7].

Dan A. Simovici in his paper “Betweenness, Metrics and Entropies in Lattices” [8] investigates a class of metrics on lattices that are compatible with the partial order defined by the lattice, using the ternary relation of betweenness that can be naturally defined on a metric space. The relationships between entropy-like functions and metrics defined on lattices are studied and the links between various properties of entropies and metrics are shown.

The survey paper by Ivo Düntsch and Alasdair Urquhart outlines the history of axiomatizations of betweenness relations and demonstrates that the class of betweenness relations generated by a reflexive and antisymmetric binary relation is first order axiomatizable, albeit with an infinite number of variables, see [9]. The paper points out the connection of betweenness relations with comparability graphs. Such a graph may be generated by essentially different partial orders; in contrast, betweenness relations carry, in some sense, total information: If $B$ is generated by a reflexive and antisymmetric binary relation, then this relation is determined by converse relations of the components.

Prenowitz and Jantosciak [10] introduced the concept of Join Space which is an abstract model for partially ordered sets, linear, spherical and projective geometries. A Join Space is a set $J$ with join operation $\circ :J\times J\to 2^J$ satisfying the following join axioms:

(J1) $a\in a\circ b$ (Closedness)

(J2) $a\circ b=b\circ a$ (Commutative law)

(J3) $a\circ (b\circ c)=(a\circ b)\circ c$ (Associative Law)

(J4) $(a∕b)\cap (c∕d)\ne \varnothing$ implies $(a\circ d)\cap (b\circ c)\ne \varnothing$, (where $a∕b=x:a\in b\circ x$, extension operator) (Pasch Axiom)

In the Join Space, betweenness is defined as $b$ is between $a$ and $c$ if $b\in a\circ c$. This paper has two examples of vector spaces, which are special Join Spaces, and vector spaces over an ordered field. The paper relates join spaces with ternary algebras.

Following others, Hedlíková represented the betweenness relation as a ternary relation and introduced the idea of ternary spaces. In the paper “Ternary Spaces, Media and Chebyshev Sets”, [11,12] she discusses ternary spaces. In a ternary space, a ternary relation defines a betweenness which unifies the metric, order and lattice betweenness in a vector space over a partially ordered field; and also extends betweenness to other geometric structures. This paper improves upon the existing theory of betweenness as an abstract algebraic concept. The paper also defines new concepts such as “media” and “Chebyshev sets” (ternary algebras satisfying certain special axioms of betweenness) and discusses their properties. A similar notion of betweenness can be found in [13].

Many authors followed this approach to define theories on the algebraic betweenness of ternary algebras. For example, the characterization of weakly-median graphs considered as algebras can be found in Chepoi et al. [14,15].

2 Betweenness in graphs

The theory of metric betweenness in graphs is developed along with the study of betweenness in general metric spaces. The most important and well-studied metric in graphs is the “shortest path metric” (geodesic metric) on a connected graph. The geodesic betweenness gives way to look at the set of all “metrically between” vertices defined between two vertices, thus resulting in the notion of “interval” or geodesic interval $I(u,v)$ in a graph. The first systematic study of the notion of the intervals in graphs was attempted by Mulder in 1980 [16]. Many significant properties of the interval on the real line can be found in the interval function $I$ of a graph. For example, if $x$ is a vertex, between $u$ and $v$, then $x$ is the only vertex between $u$ and $x$ and $x$ and $v$. This property implies the following, $\left(b1\right)$: if $x$ is a vertex, between $u$ and $v$, different from $u$, then $u$ is not between $x$ and $v$. $\left(b2\right)$: if $x$ is a vertex between $u$ and $v$ and $y$ is between $u$ and $x$, then $y$ is between $u$ and $v$. Similarly $\left(b3\right)$: if $x$ is between $u$ and $v$, and $y$ is between $u$ and $x$, then $x$ is between $y$ and $v$. These properties are described as a proposition in [16]. Mulder in his book [16] has used the concept of interval function $I$ to study several classes of graphs, some of them are related to algebraic structures, and some are related to other discrete mathematical structures. Several authors followed Mulder and studied the interval function $I$. The notable among them were Nieminen [17] who considered $I(u,v)$ from the point of view of a join space. A connected graph is a join space with $u\circ v=I(u,v)$ if and only if it is a strong prime convex intersection graph.

Nebesḱy attempted to characterize the interval function $I$ by taking the five betweenness properties of $I$ as classical axioms, which we mentioned above as proposition stated by Mulder in [16]. Nebesḱy proposed additional axioms and presented the characterization of $I$ in a series of papers starting from 1994, each time improving the proof, [18–21^{[18][19][20][21]}]. Also refer [22,23]. In [24], Mulder and Nebesḱy characterized $I$ by finding the minimal set of axioms required for the characterization of $I$ besides the five classical betweenness axioms.

The interval function is basically defined using the graph metric generated by the geodesics in graphs. In the literature, these intervals are also called geodesic intervals.

3 Betweenness through transit functions

The studies on the interval function of a connected graph using geodesics motivated the analogous study using other types of paths, the prominent among them was the induced paths instead of geodesics. Induced paths are paths without having any edges between non-consecutive vertices of the paths. One can also study the coarsest path intervals consisting of every path, known as the All paths interval. Generalizing these notions in graphs, Mulder in [25] introduced Transit functions on discrete structures with the aim to axiomatize the concept of betweenness. Following Mulder, betweenness has been extensively studied on connected simple graphs with the three basic transit functions, namely the interval function, induced path function and all-paths function as models. Our concern in this paper is to give a brief survey on these three standard path functions on finite connected simple graphs and to look at the study of betweenness as a tool for studying graph families. A transit function is an abstract notion of an interval. A transit function $R$ defined on a nonempty set $V$ is a function $R:V\times V\to 2^V$ satisfying the three (transit) axioms

(t1)	$x\in R(x,y)$ for all $x,y\in V$,

(t2)	$R(x,y)=R(y,x)$ for all $x,y\in V$,

(t3)	$R(x,x)=x$ for all $x\in V$.

The underlying graph $G_R$ of a transit function $R$ is the graph with vertex set $V$, where two distinct vertices $u$ and $v$ are joined by an edge if and only if $R(u,v)=u,v$. Basically, a transit function on a simple connected undirected graph $G$ describes how we can get from vertex $u$ to vertex $v$: via vertices in $R(u,v)$. An element $x\in R(u,v)$, can be considered as “between” the points $u$ and $v$ and hence the set $R(u,v)$ consisting of the set of all elements between $u$ and $v$ abstracts the notion of an interval on set $V$.

The interval function of a connected graph $G$ is defined as $I(u,v)=w\in V:w\text{lies on a shortest}u,v\text{-path}.$

The induced paths naturally generalizes the shortest path in the sense that every shortest path is an induced path and replacing shortest paths by induced paths in the previous definition, we obtain the induced path transit function, which is defined as $J(u,v)=w\in V:w\text{lies on an induced}u,v\text{-path}.$Replacing shortest paths or induced paths by any path in the graph, we obtain the all-paths transit function of $G$, defined as $A(u,v)=w\in V:w\text{lies on some}u,v\text{-path}.$For a transit function $R$ on a non-empty set $V$, the following betweenness axioms are natural.

(b1)	$x\in R(u,v)⟹v\notin R(u,x)$

(b2)	$x\in R(u,v)$, then $R(u,x)\subseteq R(u,v)$

(b3)	If $x\in R(u,v)$ and $y\in R(u,x)$, then $x\in R(y,v)$

(b4)	If $x\in R(u,v)$, then $R(u,x)\cap R(x,v)=x$

(m)	If $x,y\in R(u,v)$ then $R(x,y)\subseteq R(u,v)$.

Mulder in [25], termed the axioms (b1) and (b2) as betweenness and the axiom (m) is known as monotone axiom. By $R(u,v,w)$ we mean $R(u,v)\cap R(v,w)\cap R(w,u)$. Also if $V$ is a vertex set of some graph then we say $R$ is a transit function defined on the graph $G$.

4 The interval function of arbitrary graphs

An interesting problem initiated by Nebeský and finally settled by Mulder and Nebeský for the interval function of a connected graph is the following. Given some function $R:V\times V\to 2^V-\varnothing$, what properties should $R$ have to make it the interval function of some connected graph with vertex set V. Mulder in [16] described some simple properties of the interval function $I$ without any reference to the graph. The proposition is stated below.

Proposition 1

[16]

(t1)	=	$u,v\in I(u,v)$ for all $u,v$,
(t2)	=	$I(v,u)=I(u,v)$ for all $u,v$,
(b2)	=	if $x\in I(u,v)$ and $y\in I(u,x)$, then $y\in I(u,v)$ for all $u,v,x,y$,
(b3)	=	if $x\in F(u,v)$ and $y\in I(u,x)$, then $x\in I(y,v)$ for all $u,v,x,y$,
(b4)	=	if $x\in I(u,v)$, then $I(u,x)\cap I(x,v)=x$ for all $u,v,x$.

From Proposition 1, it is obvious that the interval function $I$ of any connected graph satisfies the axiom (t1), (t2), (b2), (b3) and (b4). Hence these axioms were termed as five classical axioms for interval function.

In 1994 Nebeskỳ, in [26], presented first such an axiomatic characterization of the interval function of a connected graph by considering the five classical axioms defined on a function $R$ from $V\times V\to 2^V$ of a connected graph $G=(V,E)$. To characterize $R=I$ Nebeskỳ used the following two additional axioms.

VII.	If $u,x,v,y\in E,x\in R(u,v),y\in R(u,v)$ and $u\in R(x,y)$, then $v\in R(x,y)$;

VIII.

If $u,x,v,y\in E,x\in R(u,v),y\notin R(u,v)$ and $x\notin R(u,y)$, then $v\in R(x,y)$

Nebeskỳ proved the following theorem.

Theorem 1

[26]

Let $R$ be a function defined on the vertex set $V$ of a connected graph $G$. Then $R=I$ if and only if $R$ satisfies the axioms VII and VIII.

In 2001 Nebeskỳ improved the characterization of the interval function of a connected graph $G$ in [20], in which he defined the notion of a geometric function. A geometric function $R$ on $V$ is a function satisfying (t1), (t2), (b2) and (b3). The axioms (b2) and (b3) can be combined to a simple axiom as:

(ge)	if $v\in R(u,x)$ and $y\in R(v,x)$, then $v\in R(u,y)$ and $y\in R(u,x)$; $x\in R(u,x),\forall$ $u,v,x,y\in W$.

Nebeskỳ’s second characterization of the interval function uses the following three axioms [20].

(X)	If $u,x,v,y\in E,u,v\in R(x,y)$ and $x\in R(u,v)$ then $y\in R(u,v)$ (for all $u,v,x,y\in V$);

(Y)	If $u,x,v,y\in E$ and $x\in R(u,v)$, then either $v\in R(x,y)$ or $x\in R(u,y)$ or $y\in R(u,v)$ (for all $u,v,x,y\in V$).

(Z)	if $u\ne x$, then there exists $v\in R(u,x)$ such that $u,v\in E$ (for all $u,x\in V$).

The main theorem in [20] is stated as:

Theorem 2

[20]

Let $R$ be a geometric function associated with a connected graph $G$. Then $R$ is the interval function of $G$ if and only if $R$ satisfies the axioms (X), (Y), and (Z).

In 2009, Mulder and Nebeskỳ [27], in search of an optimal characterization of the interval function in the sense of a minimal set of axioms required to characterize the interval function observed that a function $R$ must satisfy the five classical axioms if it were the interval function $I$. They searched for minimal set of additional axioms required to characterize the interval function. The additional axioms were termed as $\left(s1\right)$ and $\left(s2\right)$ and are defined as

(s1)	If $R(u,\bar{u})=u,\bar{u}$ and $R(v,\bar{v})=v,\bar{v}$, $u\in R(\bar{u},\bar{v})$ and $\bar{u},\bar{v}\in R(u,v)$, then $v\in R(\bar{u},\bar{v})$ for all $u,\bar{u},v,\bar{v}$.

(s2)	If $R(u,\bar{u})=u,\bar{u}$ and $R(v,\bar{v})=v,\bar{v}$, $\bar{u}\in R(u,v)$, $\bar{v}\notin R(u,v)$, and $v\notin R(\bar{u},\bar{v})$, then $\bar{u}\in R(u,\bar{v})$ for all $u,\bar{u},v,\bar{v}$.

The theorem characterizing the interval function is stated as:

Theorem 3

[27]

Let $R$ be a function on $V\times V\to 2^V-\varnothing$satisfying five classical axioms with underlying graph $G$ and let $I$ be the interval function of $G$. The following statements are equivalent:

(a) $R=I$,

(b) $R$ satisfies axioms $\left(s1\right)$ and $\left(s2\right)$.

The characterization of the interval function $I$ of a connected graph $G$ due to Mulder and Nebeský is generalized to arbitrary graphs including disconnected graphs recently by Changat et al. in [28]. The interval function $I_G$ can be naturally extended in a disconnected graph $G$ by defining $I_G(u,v)=z:z$ lies in some shortest $u,v$-path , if $u$ and $v$ belong to the same component of $G$ (a $\mathit{component}$ of $G$ is a maximal connected subgraph of $G$), and $I_G(u,v)=\varnothing$, if $u$ $v$ belong to different components of $G$. In this characterization, axiom $\left(t1\right)$ is adapted to a weaker axiom $\left(t{1}^{\ast }\right)$ and $\left(t3\right)$ is modified to $\left(t{3}^{\ast }\right)$, further a new axiom, namely $\left(\mathit{Compt}\right)$ is introduced for components. The new sets of axioms are the following.

(t1∗)

If $R(u,v)\ne \varnothing$ then $u\in R(u,v)$, for all $u,v$ in $V$.

(t3∗)

$R(u,u)\ne \varnothing$, for all $u$ in $V$.

(Compt)

If $R(u,v)\ne \varnothing$ and $R(v,w)\ne \varnothing$, then $R(u,w)\ne \varnothing$.

The theorem is stated as follows.

Theorem 4

[28]

Let $R:V\times V\to 2^V$ be a function on the nonempty set $V$. Then $R$ satisfies the axioms $\left(t{1}^{\ast }\right)$, $\left(t2\right)$, $\left(b2\right)$, $\left(b3\right)$, $\left(b4\right)$, $\left(s1\right)$, $\left(s2\right)$, $\left(t{3}^{\ast }\right)$ and $\left(\mathit{Compt}\right)$ if and only if $R$ is the interval function of $G_R$.

5 Interval function of special graph families

One can easily observe that the axioms that are introduced so far are first-order axioms (that is axioms which can be framed in the language of first-order logic). Thus the first order axiomatization of the interval function of an arbitrary connected graph due to Nebeskỳ and finally by Mulder and Nebeskỳ naturally pose the following questions.

Is it possible to axiomatically characterize the interval function of some special graphs using some set of first-order axioms defined on an arbitrary transit function? Is it possible to characterize the graphs with the help of their interval functions?

In this paper, we survey the results as answers to these questions and here onwards by axiom, we mean first order axioms.

Formally the two questions can be framed as follows.

•	(Problem 1): Introduce a particular betweenness axiom $\left(\alpha \right)$ and characterize the graphs for which the interval function satisfies axiom $\left(\alpha \right)$

•	(Problem 2): Characterize the interval function of a particular graph $G$ using betweenness axioms for an arbitrary transit function $R$ defined on $V\left(G\right)$.

To answer (Problem 2), introduce a set $S$ of betweenness axioms for a transit function $R$ on a non-empty set $V$, so that the interval function $I_{G_R}$ is isomorphic to $R$ satisfying the axioms in $S$ and $G_R$ isomorphic to $G$.

A bipartite graph is a graph $G$ whose vertex set can be partitioned into two sets $A$ and $B$ so that each edge in the graph has one end in $A$ and the other end in $B$.

A graph $G$ is said to be a median graph if for all $u,v,w\in V\left(G\right)$, $I(u,v)\cap I(v,w)\cap I(w,u)=1$, where $I$ is the interval function of the graph. Graphs which satisfy $I(u,v,w)\ne \varnothing$ are known as modular graphs. It can be easily seen that modular graphs are bipartite. By an interval structure, we mean a transit function which satisfies the axiom (m) and $R(u,v,w)\ne \varnothing$. A connected graph $G$ is called as interval monotone if the interval function $I_G$ satisfies the monotone axiom $\left(m\right)$.

As the first instance of the graph for problems $\left(1\right)$ and $\left(2\right)$, we consider median graphs, and the corresponding results due to Mulder in [16] is stated as follows.

Theorem 5

[16]

Let $G$ be a connected graph with interval function $I$. Then $G$ is a median graph if and only if $G$ is interval monotone and $I$ satisfies the condition that if $I(u,v)\cap I(v,w)=v$, then $v\in I(u,w)$.

Moreover Mulder proved.

Theorem 6

[16]

A connected graph $G=(V,E)$ is a median graph if and only there exists a median interval structure $R$ on $V$ such that $G_R$ isomorphic to $G$ and the interval function $I_G$ is isomorphic to $R$.

We describe the status of the interval function on one of the classical axiom from geometry, namely the Pasch Axiom. The Pasch axiom is defined for an arbitrary transit function as follows.

Pasch Axiom: For all $p,a,b\in V$ and $a^{\prime }\in R(p,a),b^{\prime }\in R(p,b)$, the intervals $R(a,b^{\prime })$ and $R(a^{\prime },b)$ have nonempty intersection. The Pasch axiom is a strong axiom and implies the axiom $\left(b3\right)$, for an arbitrary transit function. The class of connected graphs for which the interval function satisfies the Pasch axiom form an interesting class of graphs, generalizing the median graphs. This is observed by Chepoi in [29], where he proved equivalent assertions of Pasch Axiom for an arbitrary transit function and as a special case for the interval function of a connected graph. For this, we need the following definitions. A convexity on a non-empty finite set $X$ consists of $X$ together with a collection $\mathcal{C}$ of subsets of $X$, called convex sets such that: (a) the empty set and the set X are convex and (b) the intersection of convex sets is convex. For a convexity $(X,\mathcal{C})$, a convex subset of $X$ whose complement (as set complement) is also convex is called a half space. Two disjoint subsets $A,B$ in $X$ are separated by a half space $H$ provided $A\subset H$ and $B\subset X\setminus H$. $(X,\mathcal{C})$ is said to fulfill the separation axiom $S_4$ if any pair of disjoint convex sets in $X$ can be separated by a half space. It can be observed that every transit function $R$ on a non-empty set $X$ has an associated convexity, namely $R$-convexity, where, a subset $K$ of $X$ is $R$-convex, provided $R(x,y)\subset K$, for every $x,y\in K$. The convexity associated with the interval function of a connected graph is known as the geodesic convexity. The following theorem characterizes the interval function of a connected graph satisfying the Pasch axiom.

Theorem 7

[29]

The interval function $I$ of a connected graph $G$ satisfies the Pasch Axiom if and only if the corresponding geodesic convexity of $G$ is $S_4$.

A subgraph $H$ of the graph $G$ is an isometric subgraph of $G$ if the distance $d_H(u,v)$ between any two points $u$ and $v$ in $H$ equals their distance $d_G(u,v)$ in the larger graph $G$. A graph $H$ can be embedded isometrically into a graph $G$ if $H$ may be represented as an isometric subgraph of $U$. For $n\ge 0$, the $n$-dimensional hypercube is the graph on vertices representing all 0, 1-tuples of length $n$, where two vertices are adjacent whenever the tuples differ in exactly one position. A graph $G$ is weakly modular if its shortest-path metric $d$ satisfies the following two conditions namely, the Triangle Condition (TC) and the Quadrangle Condition (QC):

(TC)	=	for any three vertices $u,v,w$ with $1=d(v,w)<d(u,v)=d(u,w)$ there exists a common neighbor $x$ of $v$ and $w$ such that $d(u,x)=d(u,v)-1$;
(QC)	=	for any four vertices $u,v,w,z$ with $d(v,z)=d(w,z)=1$ and $2=d(v,w)\le d(u,v)=d(u,w)=d(u,z)-1$, there exists a common neighbor $x$ of $v$ and $w$ such that $d(u,x)=d(u,v)-1$.

Weakly median graphs are weakly modular graphs in which the vertex $x$ in the triangle and quadrangle conditions is unique. Weakly median graphs form an interesting class of non-bipartite generalizations of median graphs. In [29], Chepoi also identified the connected graphs (bipartite and non-bipartite graphs separately) whose interval function satisfies the Pasch axiom. Among non-bipartite graphs, the class of graphs whose interval function satisfies the Pasch axiom are precisely the weakly median graphs.

The graphs which are isometrically embeddable into hypercubes are known as partial cubes. Median graphs form an important class of partial cubes.

Chepoi in [29], proved that among bipartite graphs, the class of graphs whose interval function satisfies Pasch axiom are a subclass of partial cubes.

To describe the Partial cubes whose interval function satisfies Pasch axiom, Chepoi et al., introduced the following terms and definitions [30].

A connected graph $G=(V,E)$ is a partial cube if and only if $G$ is bipartite and for any edge $uv$, the sets $W(u,v)=x\in V:d(x,u)<d(x,v)$ and $W(v,u)=x\in V:d(x,v)<d(x,u)$ are convex [31]. In this case, $W(u,v)\cup W(v,u)=V$, whence $W(u,v)$ and $W(v,u)$ are half spaces. It is also known that any convex subgraph $G^{\prime }$ of a partial cube can be represented as the intersection of half spaces of $G$ [32–34^[32][33][34]]. A contraction of $G$ is the partial cube $G^{\prime }$ obtained from $G$ by contracting all edges corresponding to a given coordinate in a hypercube embedding. Now, a partial cube $H$ is called a partial cube-minor (pc-minor) of $G$ if $H$ can be obtained by a sequence of contractions from a convex subgraph of $G$. If $T_1,\dots ,T_m$ are finite partial cubes, then $\mathcal{F}(T_1,\dots ,T_m)$ is the set of all partial cubes $G$ such that no $T_i,i=1,\dots ,m$, can be obtained as a pc-minor of $G$.

It is proved that partial cubes whose interval function satisfies Pasch axiom are precisely $\mathcal{F}(T_1,\dots ,T_6)$ where $T_i$’s are isometric subgraphs of $Q_4$ depicted in Fig. 1[34,35,29,30].

Fig. 1 Isometric subgraphs of $Q_4$ which are minimal forbidden pc-minors for Pasch axiom.

The following axioms are considered by Changat et al. in [36].

(J0)	For any pairwise distinct elements $u,v,x,y\in V$ such that $x\in R(u,y)$ and $y\in R(x,v)$, we have $x\in R(u,v)$.

(J1)	$w\in R(u,v),w\ne u,v,⟹$ there exists $u_1\in R(u,w)\setminus R(v,w),v_1\in R(v,w)\setminus R(u,w)$, such that $R(u_1,w)=u_1,w,R(v_1,w)=v_1,w$ and $w\in R(u_1,v_1)$.

(J2)	$R(u,x)=u,x,R(x,v)=x,v,u\ne v,R(u,v)\ne u,v⟹x\in R(u,v)$.

(J3)	$x\in R(u,y),y\in R(x,v),x\ne y,u\ne v,R(u,v)\ne u,v⟹x\in R(u,v)$.

(J2’)

$x\in R(u,y),y\in R(x,v),x\ne y,R(u,x)=R(x,y)=R(y,v)=2,u\ne v,R(u,v)\ne u,v⟹x\in R(u,v)$.

(J3’)

$x\in R(u,y),y\in R(x,v),R(x,y)\ne x,y,x\ne y,u\ne v,R(u,v)\ne u,v⟹x\in R(u,v)$.

We need the following graphs in the sequel. By a long cycle (Hole) we mean a cycle of length at least 5 (see Figs. 2 and 3).

Fig. 2 The long cycle (Hole), $4$-fan, $P$ graph.

Fig. 3 Claw, Paw.

A chordal graph is a graph with no induced cycles of length more than $3$. We say that a graph $G$ is free from a graph $H$ if $G$ does not contain $H$ as an induced subgraph. Let $\mathcal{H}$ be a family of graphs $H_1,\dots ,H_k$. We say $G$ is $\mathcal{H}$-free if $G$ has no induced subgraph isomorphic to $H_i$ for $i=1,\dots ,k$. Changat et al. in [37] proved the following two theorems.

Theorem 8

[37]

Let $G$ be a connected graph with the interval function $I$ satisfy the axiom (J3) if and only if the graph $G$ is free from House, Hole, the $P$-graph, and $3$-fan.

Theorem 9

[37]

$I$ on a connected graph $G$ satisfies the axiom (J0) if and only if $G$ is a chordal graph that is $3$-fan free.

Sholander in 1952 in [38] gave a characterization of the interval function of a tree without a complete proof. The completion of the proof was presented by Chvàtal et al. in [39]. Sholander’s axioms were the following.

(S)	There exists an $x$ such that $R(u,v)\cap R(v,w)=R(x,v)$, for all $u,v,w\in V$.

(T)	$R(u,v)\subseteq R(u,w)⟹R(u,v)\cap R(v,w)=v$, for all $u,v,w\in V$.

(U)	$R(u,x)\cap R(x,v)=x⟹R(u,x)\cup R(x,v)=R(u,v)$, for all $u,v\in V$.

Sholander [38] proved that his axioms (S) and (T) imply the five classical axioms and also stated that a function $R$ defined on the vertex set $V$ of a connected graph $G$ satisfies the axioms (S), (T) and (U) if and only if $G$ is a tree and $R$ coincides with the interval function (Sholander used the term segment function for the interval function, a formal proof of this theorem is due to Chvàtal et al. in [39]).

A block graph is a graph in which each block is complete. In [40], Balakrishnan et al. extended the characterization of the interval function of trees to block graphs, a natural generalization of trees. For this, the axiom (U) is modified to (U*) defined as : $R(u,x)\cap R(x,v)=x⟹R(u,v)\subseteq R(u,x)\cup R(x,v)$, for all $u,v\in V$. The following theorem is proved.

Theorem 10

[40]

Let $R:V\times V\to 2^V$ be a function on $V$. Then $R$ satisfies axioms (t1), (t2), (b1), (b2) and (U*) if and only if $G_R$ is a block graph and $R=I_{G_R}$.

For graphs which are complete or a tree, the following theorem is proved.

Theorem 11

[40]

Let $R:V\times V\to 2^V$ be a function on $V$. Then $R$ satisfies axioms (t1), (t2), (b1), (b2) and (U’) if and only if $G_R$ is a tree or a complete graph and $R=I_{G_R}$, where (U’) is a modification of (U) defined as $R(u,x)\cap R(x,v)=x,R(u,v)\ne u,v\Rightarrow R(u,x)\cup R(x,v)=R(u,v)$, for all $u,v,x$ in $V$.

The authors also presented new characterizations of the interval function of a tree using weaker axioms than that of Sholander [38] and Chvàtal et al. [39].

Theorem 12

[40]

Let $R:V\times V\to 2^V$ be a function on $V$. Then $R$ satisfies axioms (t1), (t2), (b1), (b2) and (U) if and only if $G_R$ is a tree and $R=I_{G_R}$.

The following proposition and theorem have been also proved.

Proposition 2

[40]

Let $R:V\times V\to 2^V$ be a function on $V$. Then $R$ satisfies axioms (t1), (t2), (b1), (b2) and (U). Then each component of $G_R$ is a tree, and $R=I_H$ on each component $H$ of $G_R$.

Theorem 13

[40]

Let $R:V\times V\to 2^V$ be a function on $V$ . Then $G_R$ is connected and $R$ satisfies axioms (t1), (t2) and (U) if and only if $G_R$ is a tree and $I_{G_R}=R$.

A complete bipartite graph is a bipartite graph in which every pair of vertices in the partite classes are adjacent. In [41] Changat et al. gave a characterization of interval function of a bipartite graph. For that, they introduced the following axiom.

(bp)	for any $x,y,z\in V$, $R(x,y)=x,y\Rightarrow y\in R(x,z)$ or $x\in R(y,z)$.

They have proved the following theorem.

Theorem 14

[41]

Let $R$ be a transit function on a finite set $V$ and $G_R$ be the underlying graph of $R$, then $R$ satisfies axioms $\left(b3\right)$, $\left(b2\right)$ and $\left(bp\right)$ if and only if $G_R$ is a bipartite graph and $I_{G_R}=R$.

With the help of another axiom $\left(cbp\right)$, they derived a characterization of the interval function of complete bipartite graphs.

(cbp)

For distinct $x,y,z\in V$, if $z\in R(x,y)$, then $R(x,z)=x,z$ and $R(z,y)=z,y$.

Theorem 15

[41]

Let $R$ be a transit function, then $R$ satisfies axioms $\left(bp\right)$ and $\left(cbp\right)$ if and only if $G_R$ is a complete bipartite graph and $I_{G_R}=R$.

In [42] Changat et al. introduced the following axioms and characterized the claw–paw-free graphs.

(cp)	for any pairwise distinct vertices $a,b,c,d\in V$, $b\in R(a,c)$ and $b\in R(a,d)\Rightarrow c\in R(b,d)$ or $d\in R(b,c)$.

(d2)	$\forall x\in V$, $\exists y,z\in V$, $x\ne y\ne z$ such that $R(x,y)=x,y$ and $R(x,z)=x,z$.

The following theorems are proved in [42].

Theorem 16

[42]

The interval function $I$ of a connected graph $G$, satisfies axiom $\left(cp\right)$ if and only if $G$ is a claw and paw-free graph.

Theorem 17

[42]

A transit function $R$ on a finite nonempty set $V$ satisfies axioms $\left(b1\right)$, $\left(b2\right)$, $\left(cp\right)$, $\left(s1\right)$ and $\left(s2\right)$ if and only if $G_R$ is claw and paw-free and $R=I_{G_R}$.

A graph $G$ is a Hamiltonian graph if it contains a spanning cycle — a cycle that contains all its vertices.

Theorem 18

[42]

A transit function $R$ on a nonempty set $V$, $V\ge 3$, satisfies axioms $\left(b1\right)$, $\left(b2\right)$, $\left(cp\right)$, $\left(d2\right)$, $\left(s1\right)$ and $\left(s2\right)$ if and only if $G_R$ is claw and paw-free and Hamiltonian and $R=I_{G_R}$.

Nebeský introduced the following two axioms

$\left(g1\right)$	=	if $x\in R(u,v)$ , then $R(u,v)=R(u,x)\cup R(x,v)$ for all $u,x,v\in V$,
$\left(g2\right)$	=	if $R(u,x)=2=R(v,y)$ and $x\in R(u,v)$, then $x\in R(u,y)$ or $v\in R(x,y)$ for all $u,v,x,y\in V$.

The following theorem characterizes the interval function of geodetic graphs, which is due to Nebeský.

Theorem 19

[21]

Let $R:V\times V\to 2^V$ be a function on $V$. Then $R$ satisfies axioms $\left(t1\right)$, $\left(t2\right)$, $\left(b4\right)$, $\left(g1\right)$ and $\left(g2\right)$ if and only if $G_R$ is geodetic and $R=I_{G_R}$.

6 Induced path transit function of special graph families

Nebeský in [43], has established that an axiomatic characterization of the induced path transit function of an arbitrary connected graph using first-order betweenness axioms like that of the interval function $I$ is impossible. As a consequence of this seminal result, the problems that we can pose for the induced path transit functions are:

•	(Problem 3): Introduce a particular betweenness axiom $\left(\alpha \right)$ and characterize the graphs for which the induced path transit function satisfies axiom $\left(\alpha \right)$

•

(Problem 4): Characterize the induced path transit function of a particular graph $G$ using betweenness axioms for an arbitrary transit function $R$ defined on $V\left(G\right)$. For this introduce a set $S$ of betweenness axioms for a transit function $R$ on a non-empty set $V$ so that the induced path transit function $J_{G_R}$ is isomorphic to $R$ satisfying the axioms in $S$ and $G_R$ isomorphic to $G$.

Mulder et al. in [44], proved the following theorems.

Theorem 20

[44]

The induced path transit function $J$ of a connected graph $G$ satisfies axioms (b1) and (b2) if and only if $G$ does not contain the long cycle, the house or the domino as an induced subgraph.

Theorem 21

[44]

Let $G$ be a connected graph. $J(u,v,w)=0$ for any distinct $u,v,w\in V\left(G\right)$ if and only if $G$ is a complete graph.

Theorem 22

[44]

Let $G$ be a connected graph. $J(u,v,w)=1$ for any triple of vertices $u,v,w$, if and only if every block in $G$ is a $K_2$ or a $4$-cycle.

Theorem 23

[44]

The induced path transit function $J$ of a connected graph $G$ satisfies (b3) axiom if and only $J$ satisfies axioms (b1), (b2) and $G$ is $3$-fan free, that is $G$ is $HHD,3$-fan free.

In [45], a family of graphs ${\tilde{K}}_{2,3}$ is constructed by Changat et al. from the complete bipartite graph $K_{2,3}$ as follows: Let $u$ and $v$ be the degree three vertices of $K_{2,3}$. Let $p,q$ and $z$ be its degree two vertices. Subdivide the path $u\to z\to v$ and make $p$ adjacent with some internal vertices of $u\to z\to v$ so that the neighbors of $u$ and $v$ on $u\to z\to v$ on the subdivided graph are adjacent to $p$. Changat et al. proved the following theorem.

Theorem 24

[45]

If $G$ is a connected graph which is $K_{2,3}$- and ${\tilde{K}}_{2,3}$-free. Then the induced path transit function $J$ of $G$ satisfies (b2) if and only if it is monotone.

Changat et al. proved the following results in [36], for the induced path transit function.

Theorem 25

[36]

The induced path transit function $J$ of a connected graph satisfies the axiom (J1) if and only if the graph $G$ is $HHD$-free.

Theorem 26

[36]

$J$ is a transit function on a non-empty finite set $V$ satisfying the axioms $\left(b1\right),\left(J2\right)$ and $\left(J3\right)$ with underlying graph $G_J$. Then $G_J$ is $HHP$-free.

Theorem 27

[36]

if $J$ is a transit function on a non-empty finite set $V$ satisfying the axioms (b1), (J2), (J2’) and (J3’) with underlying graph $G_J$. Then $G_J$ is $HHD$-free.

Theorem 28

[36]

Let $V$ be a finite non-empty set and $J$ be a transit function on $V$ satisfying the axioms (b1), (b2), (J1), (J2) and (J3). Let $G_J$ be the underlying graph of the transit function $J$. Then $J$ is precisely the induced path function of $G_J$.

Theorem 29

[36]

Let $V$ be a finite non-empty set and $J$ be a transit function on $V$ satisfying the axioms (b1), (b2), (J1), (J2), (J2’), (J3’). Let $G_J$ be the underlying graph of the transit function $J$. Then $J$ is precisely the induced path function of $G_J$.

Theorem 30

[36]

Let $G=(V,E)$ be a connected $HHP$-free graph, and let $J$ be the induced path function of $G$. Then $J$ satisfies the axioms (b1), (b2), (J1), (J2) and (J3).

Theorem 31

[36]

Let $G=(V,E)$ be a connected $HHD$-free graph, and let $J$ be the induced path function of $G$. Then $J$ satisfies the axioms (b1), (b2), (J1), (J2), (J2’), and (J3’).

A wheel $W_n$ is a graph formed by connecting a single vertex to all vertices of an $n$-cycle $C_n$. The edges adjacent with the single vertices are known as spokes. $W_n^{-}$ is the graph obtained from $W_n$ by deleting a spoke.

Theorem 32

[36]

Let $G=(V,E)$ be a connected graph that is $HHP$-free, $K_{2,3}$-free, and $W_4^{-}$-free, and let $J$ be the induced path function of $G$. Then $J$ satisfies (b1), (m), (J1), (J2), and (J3).

Theorem 33

[36]

Let $G=(V,E)$ be a connected graph that is $HHD$-free, $K_{2,3}$ -free, $W_4^{-}$-free, and let $J$ be the induced path function $G$. Then $J$ satisfies (b1), (m), (J1), (J2), (J2’) and (J3’).

Changat et al. also proved the following theorems.

Theorem 34

[37]

$J$ satisfies (b4) on a connected graph $G$ if and only if $G$ is $HHD$ and $4$-fan free.

Theorem 35

[37]

$J$ satisfies the axiom (J0) on a connected graph $G$ if and only if $G$ is a chordal graph.

Changat et al. also proved the following results.

Theorem 36

[41]

The induced path transit function $J$ of a connected graph $G$ satisfies axiom $\left(bp\right)$ if and only if $G$ is triangle-free.

Theorem 37

[41]

Let $R$ be a transit function on a nonempty finite set $V$ then $G_R$ is either $C_4$ or tree if and only if $R$ satisfies axioms $\left(b2\right)$, $\left(bp\right)$, $\left(j1\right)$ and $\left(j3\right)$ and $J_{G_R}=R$.

A similar result for the induced path transit function as that of the interval function with respect to the axiom $\left(cp\right)$ is proved in [42].

Theorem 38

[42]

The induced path transit function $J$ of a connected graph $G$, satisfies axiom $\left(cp\right)$ if and only if $G$ is a claw and paw-free graph.

In [46], Changat et al. characterized the class of graphs for which induced path transit functions satisfy Pasch axiom.

Let $\mathcal{F}$ denote the following family of graphs: cycles $C_n$ for $n\ge 5$, domino, house, x-house, 3-fan, $K_{2,3}$, $K_{2,3}^{+}$, and $W_4^{-}$. All graphs of family $\mathcal{F}$ are depicted in Fig. 4. By $\mathcal{F}$-free graphs we mean all graphs which have no subgraph isomorphic to a graph from the family $\mathcal{F}$ as an induced subgraph. The following theorem characterizes the induced path transit function of a connected graph satisfying the Pasch axiom.

Fig. 4 Domino, house, $x$-house, 3-fan (depicted from left to right above), and $K_{2,3}$, $K_{2,3}^{+}$ and $W_4^{-}$ (from left to right below and long cycle (hole)).

Theorem 39

[46]

For a connected graph $G$ the following statements are equivalent:

(i)	the induced path transit function $J$ of $G$ satisfies the Pasch axiom;

(ii)	$G$ is an $\mathcal{F}$-free graph;

(iii)

for every block $B$ of $G$ and every $u\in V\left(B\right)$, $de{g}_B\left(u\right)\ge V\left(B\right)-2$.

Also, we have the theorem characterizing an arbitrary transit function $R$ satisfying the Pasch axiom such that the induced path transit function of its underlying graph coincides with $R$.

Theorem 40

[46]

A graph $G$ is a connected $\mathcal{F}\cup P$-free graph if and only if there exists a transit function $R$ satisfying the Pasch axiom and axioms $\left(b2\right)$, $\left(J1\right)$, $\left(J2\right)$ and $\left(J3\right)$, such that $G$ is the underlying graph of $R$.

7 The all paths transit function

Recall that the All paths function is the coarsest path transit function. Changat et al. in [47], characterized the all paths transit function of a graph with the axioms (b2), (U) and

(A6)

=

$A(u,v)⫋A(u,w),u\ne v⟹\exists x\in A(u,v),x\ne u$ such that $A(u,x)\cap A(x,w)=x$.

Let $A$ be a transit function defined on a set V. We define the transit graph $G_A$ of $A$ as follows. It has $V$ as the vertex set and $u,v$ is an edge of $G_A$ if there is no $x\ne u,v$ such that $A(u,x)\cap A(x,v)=x$.

Theorem 41

[47]

Let $A$ be a transit function on a set V satisfying (b2), (U) and (A6), and let $G_A$ be the transit graph of $A$. Then $A$ is the all-paths transit function of $G_A$.

8 Concluding remarks

In this short survey, we have mainly discussed the interval function and the induced path transit function of graphs, representing the shortest path and the induced betweenness respectively as solutions to Problems $1,2,3$ and $4$. We have surveyed almost all the known results from the literature. One can consider new sets of first-order axioms and attempt problems $1,2,3$ and $4$, providing more results on the shortest and the induced path betweenness, respectively. It will be interesting to give the axiomatic characterization of the interval and induced path transit functions of some standard graph families. In particular chordal graphs and its subfamilies like interval graphs, unit interval graphs may be attempted. Now we have the axiomatic characterization of interval function of partial cubes excluding those partial cubes with the pc minors depicted in Fig. 1. It will be interesting to attempt the axiomatic characterization of interval function of all partial cubes.

Notes

This work was supported by NBHM DAE under file NBHM/2/48(9)/2014/NBHM (R.P.)/R&D-II/4364.

Peer review under responsibility of Kalasalingam University.