zbMATH — the first resource for mathematics

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.

05C75 Structural characterization of families of graphs
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Biggs, N., Algebraic graph theory, (1974), Cambridge Univ. Press London · Zbl 0284.05101
[2] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), 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.
[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, () · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.