Cycle-regular graphs of \((0,\lambda )\)-graph type (Q960922)

A connected simple graph \(G\) is a \textit{\((0,\lambda )\)-graph}, introduced by \textit{M. Mulder} [``\((0,\lambda)\)-graphs and \(n\)-cubes,'' Discrete Math. 28, 179--188 (1979; Zbl 0418.05034)], if every pair of distinct vertices have exactly \(\lambda\) common neighbors or none at all. Hadamard graphs and hypercubes are examples of \((0, \lambda )\)-graphs. \textit{M. Mollard} [``Cycle-regular graphs,'' Discrete Math. 89, No. 1, 29--41 (1991; Zbl 0726.05044)] defined a graph \(G\) to be an \textit{\([l, \lambda]\)-cycle-regular graph} if there is a nonempty subset \({\mathcal C}\) of cycles in \(G\) such that every path in \(G\) of length \(l\) belongs to exactly \(\lambda\) cycles in \({\mathcal C}\). In particular, if \({\mathcal C}\) is the set of cycles of length \(k\) where \(k \geq 2l\), then \(G\) is an \textit{\([l, \lambda, k]\)-cycle-regular graph}. Thus \((0, \lambda )\)-graphs are \([2, \lambda - 1, 4]\)-cycle-regular graphs. Let \(H_n\) be the subgraph of the hypercube \(Q_{2n-1}\) induced by the \(n\)-subsets and \((n-1)\)-subsets of a \((2n-1)\)-element set. Two vertices \(A, B \in H_n\) are adjacent to each other if and only if \(|(A \setminus B) \cup (B \setminus A)| = 1\). The odd graphs and the graphs \(H_n\) are \([3, 1, 6]\)-cycle-regular graphs. Mollard [loc. cit.] showed that if a \([3, 1, 6]\)-cycle-regular graph \(G\) has maximum degree \(\Delta(G) = n\), then \(G\) has at most \({2n \choose n}\) vertices and the diameter \(diam(G)\) of \(G\) is at most \(2n - 1\). Also, if a \([3, 1, 6]\)-cycle-regular graph \(G\) has \(\Delta(G) = n\) and \(|V(G)| = {2n \choose n}\), then \(G = H_n\). The main result of this paper is that if a \([3, 1, 6]\)-cycle-regular graph \(G\) has \(\Delta(G) = n\) and \(diam(G) = 2n - 1\), then \(G = H_n\).