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

$$\widetilde d(x,y)=(d(x,y),d(y,x)),$$

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

$$V=\mathbb Z_3\times \mathbb Z_3$$

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

$$v-u\in S:=\{(0,1),(0,2),(1,0)\}.$$

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

$$\{(0,0)\},\quad \{0\}\times\{1,2\},\quad \{(1,0)\},\quad \{(2,0)\},\quad \{1\}\times\{1,2\},\quad \{2\}\times\{1,2\}.$$

Their two-way distances are respectively

$$(0,0),(1,1),(1,2),(2,1),(2,3),(3,2).$$

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

$$\{0\}+\{0\}=\{0\},\quad \{0\}+\{1,2\}=\{1,2\},$$

and

$$\{1,2\}+\{1,2\}$$

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

$$|\delta^+(X)| =\sum_{i\in\mathbb Z_3}\left(|X_i|(3-|X_i|)+|X_i\setminus X_{i+1}|\right).$$

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

$$|\delta^+(X)|\ge 3.$$

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

$$X=B_0=\{0\}\times\mathbb Z_3.$$

Then

$$\delta^+(X)=\{(0,a)\to(1,a):a\in\mathbb Z_3\}$$

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.