×

Interval-regular graphs. (English) Zbl 0542.05051

Summary: An 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.

MSC:

05C75 Structural characterization of families of graphs
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Biggs, N., Algebraic Graph Theory (1974), Cambridge Univ. Press: Cambridge Univ. Press London · Zbl 0284.05101
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan: Macmillan London · Zbl 1134.05001
[3] Foldes, S., A characterization of hypercubes, Discrete Math., 17, 155-159 (1977) · Zbl 0354.05045
[4] S. Foldes, Private communication.; S. Foldes, Private communication.
[5] Mulder, H. M., (0,λ)-graphs and \(n\)-cubes, Discrete Math., 28, 179-188 (1979) · Zbl 0418.05034
[6] Mulder, H. M., The interval function of a graph, (Ph.D. Thesis (1980), Vrije Universiteit: Vrije Universiteit Amsterdam) · Zbl 0446.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.