Interval-regularity does not lead to interval monotonicity
A connected graph \(G\) is interval-regular if for any two vertices \(u\) and \(v\) of \(G\) the number of neighbors of \(u\) lying on some shortest \((u,v)\)- path is equal to \(d(u,v)\). On the other hand \(G\) is interval-monotone if for any \(u\), \(v\) the set \(I(x,y)\) of vertices lying on shortest \((x,y)\)- paths is contained in the set of vertices \(I(u,v)\) on shortest \((u,v)\)- paths for \(x,y\in I(u,v)\). A 1980 conjecture of M. Mulder is that an interval-regular graph is interval-monotone. The conjecture is false: Presented is an infinite family of counterexamples reminiscent of the hypercubes \(Q_ n\).
scientific article; zbMATH DE number 417448