Minimum edge cuts of distance-regular and strongly regular digraphs

NEW

Problem: Reconstructed statement: In the category of finite loopless strongly connected digraphs, a digraph $\Gamma$ is weakly distance-regular if, writing

the number of vertices $z$ with $\widetilde d(x,z)=\alpha$ and $\widetilde d(z,y)=\beta$ depends only on $\alpha,\beta$ and $\widetilde d(x,y)$. The conjecture asserts: if $\Gamma$ is weakly distance-regular with out-valency $k$, then its edge connectivity is $k$; moreover, if $k>2$, every minimum edge cut is exactly the set of all arcs leaving one vertex or all arcs entering one vertex.

Result: The conjecture is false.

Let

and define a Cayley digraph $\Gamma$ by putting an arc $u\to v$ iff

Thus each block $B_i=\{i\}\times \mathbb Z_3$ induces a complete bidirected triangle, and each vertex $(i,a)$ has one additional arc to $(i+1,a)$. Hence $\Gamma$ is strongly connected and has valency $k=3$.

For $g=y-x$, the two-way distance $\widetilde d(x,y)$ depends only on $g$. The six weak-distance classes are

Their two-way distances are respectively

For any two such classes $P,Q$, the number of decompositions $g=p+q$, $p\in P,q\in Q$, is constant as $g$ ranges over any one of the above six classes: this follows because in the second coordinate

and

has coefficient $2$ on $0$ and coefficient $1$ on each nonzero element. Hence the intersection numbers depend only on weak-distance classes, so $\Gamma$ is weakly distance-regular.

Now compute edge connectivity. For $X\subset V$, write $X_i=\{a:(i,a)\in X\}$. The number of arcs leaving $X$ is

If some $X_i$ is nonempty and not all of $\mathbb Z_3$, then the internal term contributes at least $2$. A short case check from the displayed formula shows that every nonempty proper $X$ satisfies

Indeed, if all $X_i$ are either empty or full, then a proper nonempty cyclic pattern has a full-to-empty transition, contributing $3$. If some $X_i$ is partial, then either at least two are partial, giving at least $4$, or exactly one is partial, giving $2$ internally and at least one matching arc leaving.

Thus $\lambda(\Gamma)=3=k$. However, take

Then

has size $3$, so it is a minimum edge cut. It is not the set of all arcs leaving a single vertex, nor the set of all arcs entering a single vertex, since it has three distinct tails and contains no internal triangle arcs.

Therefore $\Gamma$ is a weakly distance-regular digraph of valency $k=3>2$ with a minimum edge cut not coming from a single vertex. This disproves the conjecture.

Verification audit: the example is finite, loopless, strongly connected, $3$-regular in- and out-degree, weakly distance-regular by the intersection-number check above, and the exhibited cut is genuinely minimum and non-star.

Citation: No existing disproof is used here. Original conjecture: S. Ashkboos, G. R. Omidi, F. Shafiei, K. Tajbakhsh, “Minimum edge cuts of distance-regular and strongly regular digraphs,” arXiv:1702.01253.