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\).
- Steiner intervals, geodesic intervals, and betweenness
- Generalized hypercubes and (0, 2)-graphs
- Induced path transit function, monotone and Peano axioms
- A remark on Mulder's conjecture about interval-regular graphs
- A characterization of the interval distance monotone graphs
- On two problems about (0, 2)-graphs and interval-regular graphs
- Spherical and Clockwise Spherical Graphs
- scientific article; zbMATH DE number 867678 (Why is no real title available?)
- Interval-regular graphs
- Interval-regular graphs of diameter two
- The induced path function, monotonicity and betweenness
This page was built for publication: Interval-regularity does not lead to interval monotonicity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685568)
