A characterization of the interval distance monotone graphs

AbstractA simple connected graph G is said to be interval distance monotone if the interval I(u,v) between any pair of vertices u and v in G induces a distance monotone graph. Aı¨der and Aouchiche [Distance monotonicity and a new characterization of hypercubes, Discrete Math. 245 (2002) 55–62] proposed the following conjecture: a graph G is interval distance monotone if and only if each of its intervals is either isomorphic to a path or to a cycle or to a hypercube. In this paper we verify the conjecture