Interval-regularity does not lead to interval monotonicity
type: Item
instance of: scholarly article
title: Interval-regularity does not lead to interval monotonicity
zbMATH Open document ID: 0784.05040
DOI: 10.1016/0012-365X(93)90064-Z
author: Michel Mollard
published in: Discrete Mathematics
publication date: 1994-03-17T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 417448
zbMATH Keywords: interval-regular graph
zbMATH Keywords: interval-monotone graph
zbMATH Keywords: shortest path
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: A characterization of hypercubes
cites work: Q3890733
cites work: Interval-regular graphs
description: scientific article; zbMATH DE number 417448