Geodesic
Minimum cuts of distance-regular digraphs
The electronic journal of combinatorics, Tome 24 (2017) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/6167
Classification : 05C20, 05C40
Mots-clés : distance-regular digraphs, strongly regular digraphs, minimum cuts, connectivity 
@article{10_37236_6167,
     author = {Saleh Ashkboos and Gholamreza Omidi and Fateme Shafiei and Khosro Tajbakhsh},
     title = {Minimum cuts of distance-regular digraphs},
     journal = {The electronic journal of combinatorics},
     year = {2017},
     volume = {24},
     number = {4},
     doi = {10.37236/6167},
     zbl = {1372.05085},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/6167/}
}
TY  - JOUR
AU  - Saleh Ashkboos
AU  - Gholamreza Omidi
AU  - Fateme Shafiei
AU  - Khosro Tajbakhsh
TI  - Minimum cuts of distance-regular digraphs
JO  - The electronic journal of combinatorics
PY  - 2017
VL  - 24
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/6167/
DO  - 10.37236/6167
ID  - 10_37236_6167
ER  - 
%0 Journal Article
%A Saleh Ashkboos
%A Gholamreza Omidi
%A Fateme Shafiei
%A Khosro Tajbakhsh
%T Minimum cuts of distance-regular digraphs
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/6167/
%R 10.37236/6167
%F 10_37236_6167
Saleh Ashkboos; Gholamreza Omidi; Fateme Shafiei; Khosro Tajbakhsh. Minimum cuts of distance-regular digraphs. The electronic journal of combinatorics, Tome 24 (2017) no. 4. doi: 10.37236/6167

Cité par Sources :