On two problems about (0, 2)-graphs and interval-regular graphs (Q2713628)

A \((0,2)\)-graph is a connected graph in which any two distinct vertices have either no common neighbour, or exactly two. An interval-regular graph is a graph in which for any two vertices \(u,v\) the number of neighbours of \(u\) lying on a shortest \((u,v)\)-paths is equal to the distance between \(u\) and \(v\). Graph operations preserving the property of being a \((0,2)\)-graph are studied. The results enable to construct non-vertex-transitive \((0,2)\)-graphs and to construct a family of regular interval-regular graphs which are not interval-monotone. The latter construction disproves a weaker version of a conjecture by H. M. Mulder.