Cycle-regular graphs (Q2277469)

A (0,\(\lambda\))-graph is understood to be a connected graph in which any two vertices have \(\lambda\) common neighbors or none at all. These graphs were introduced by \textit{M. Mulder} [ibid. 28, 179-188 (1979; Zbl 0418.05034)]. He also proved that maximum (0,\(\lambda\))-graphs are hypercubes. In the paper under review the concept of (0,\(\lambda\))-graphs is generalized in some sense as follows. We say that G is a [\(\ell,\lambda]\)-cycle regular graph if there is a nonempty subset C of elementary cycles in G such that every path in G of length \(\ell\) belongs to exactly \(\lambda\) cycles in C. If C is the set of elementary cycles of length m (m\(\geq 2\ell)\), then G is said to be a [\(\ell,\lambda,m]\)-cycle regular graph. In Section 1 the author is concerned with the regularity of [\(\ell,\lambda]\)-cycle regular graphs with minimum degree \(\delta\geq 3\). Section 2 discusses the case \(\delta (G)=2\). In Section 3 two families of [3,1,6]-cycle regular graphs are described. Finally, it turns out that maximum [3,1,6]-cycle regular graphs are also related to hypercubes.