Minimum arc-cuts of normally regular digraphs and Deza digraphs (Q2138973): Difference between revisions

By a normally regular digraph with parameters $(n, k, \lambda, \mu)$, also denoted by $\text{NRD}(n, k, \lambda, \mu)$, we mean a $k$-regular digraph on $n$ vertices such that (i) any two non-adjacent vertices have exactly $\mu$ common out-neighbours; (ii) any two vertices $x$, $y$ such that either $x\to y$ or $x\leftarrow y$ have exactly $\lambda$ common out-neighbours; (iii) any two vertices $x$, $y$ such that $x\leftrightarrow y$ have exactly $2\lambda-\mu$ common out-neighbours. By a Deza graph with parameters $(n,k, b, c)$ we mean a $k$-regular graph on $n$ vertices such that any two distinct vertices have $b$ or $c$ common neighbours. In this paper, the authors establish that a normally regular graph $\text{NRD}(n, k, \lambda, \mu)$ has $k$ as arc-connectivity. To achieve this they obtain two technical lemmas. The paper forms an interesting read and will serve as a stimulating source for further research in this direction.