Interval-regular graphs

AbstractAn interval-regular graph is a connected graph in which, for any two vertices u and v, the number of neighbours of u on all shortest (u, v)-paths equals d(u, v). It is proved that in an interval-regular graph the shortest (u, v)-paths induce a hypercube of dimension d(u, v), for any two vertices u and v. The products of complete graphs are characterized as interval-regular graphs satisfying some extra conditions. The extended odd graphs are introduced as critical example with respect to the results proved