Minimum cuts of distance-regular digraphs (Q2409834): Difference between revisions

Summary: In this paper, we investigate the structure of minimum vertex and edge cuts of distance-regular digraphs. We show that each distance-regular digraph \(\Gamma\), different from an undirected cycle, is super edge-connected, that is, any minimum edge cut of \(\Gamma\) is the set of all edges going into (or coming out of) a single vertex. Moreover, we will show that except for undirected cycles, any distance regular-digraph \(\Gamma\) with diameter \(D=2\), degree \(k\leq 3\) or \(\lambda=0\) (\(\lambda\) is the number of 2-paths from \(u\) to \(v\) for an edge \(uv\) of \(\Gamma\)) is super vertex-connected, that is, any minimum vertex cut of \(\Gamma\) is the set of all out-neighbors (or in-neighbors) of a single vertex in \(\Gamma\). These results extend the same known results for the undirected case with quite different proofs.