Geodesic
On the Optimality of 3-Restricted Arc Connectivity for Digraphs and Bipartite Digraphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 321-332.

Voir la notice de l'article provenant de la source Library of Science

Let D be a strong digraph. An arc subset S is a k-restricted arc cut of D if D − S has a strong component D′ with order at least k such that D(D′) contains a connected subdigraph with order at least k. If such a k-restricted arc cut exists in D, then D is called λk-connected. For a λk-connected digraph D, the k-restricted arc connectivity, denoted by λk(D), is the minimum cardinality over all k-restricted arc cuts of D. It is known that for many digraphs λk(D) ≤ ξk(D), where ξk(D) denotes the minimum k-degree of D. D is called λk-optimal if λk(D) = ξk(D). In this paper, we will give some sufficient conditions for digraphs and bipartite digraphs to be λ3-optimal.
Keywords: restricted arc-connectivity, bipartite digraph, optimality, digraph, network 
@article{DMGT_2022_42_2_a0,
     author = {Zhang, Yaoyao and Meng, Jixiang},
     title = {On the {Optimality} of {3-Restricted} {Arc} {Connectivity} for {Digraphs} and {Bipartite} {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {321--332},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a0/}
}
TY  - JOUR
AU  - Zhang, Yaoyao
AU  - Meng, Jixiang
TI  - On the Optimality of 3-Restricted Arc Connectivity for Digraphs and Bipartite Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 321
EP  - 332
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a0/
LA  - en
ID  - DMGT_2022_42_2_a0
ER  - 
%0 Journal Article
%A Zhang, Yaoyao
%A Meng, Jixiang
%T On the Optimality of 3-Restricted Arc Connectivity for Digraphs and Bipartite Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 321-332
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a0/
%G en
%F DMGT_2022_42_2_a0
Zhang, Yaoyao; Meng, Jixiang. On the Optimality of 3-Restricted Arc Connectivity for Digraphs and Bipartite Digraphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 321-332. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a0/

[1] C. Balbuena and P. García-Vázquez, On the restricted arc-connectivity of s-geodetic digraphs, Acta Math. Sin. (Engl. Ser.) 26 (2010) 1865–1876. https://doi.org/10.1007/s10114-010-9313-y

[2] C. Balbuena, P. García-Vázquez, A. Hansberg and L.P. Montejano, Restricted arc-connectivity of generalized p-cycles, Discrete Appl. Math. 160 (2012) 1325–1332. https://doi.org/10.1016/j.dam.2012.02.006

[3] C. Balbuena, P. García-Vázquez, A. Hansberg and L.P. Montejano, On the super-restricted arc-connectivity of s-geodetic digraphs, Networks 61 (2013) 20–28. https://doi.org/10.1002/net.21462

[4] C. Balbuena, C. Cera, A. Diánez, P. García-Vázquez and X. Marcote, Sufficient conditions for λ′ ′-optimality of graphs with small conditional diameter, Inform. Process. Lett. 95 (2005) 429–434. https://doi.org/10.1016/j.ipl.2005.05.006

[5] X. Chen, J. Liu and J. Meng, The restricted arc connectivity of Cartesian product digraphs, Inform. Process. Lett. 109 (2009) 1202–1205. https://doi.org/10.1016/j.ipl.2009.08.005

[6] X. Chen, J. Liu and J. Meng, λ ′ -optimality of bipartite bigraphs, Inform. Process. Lett. 112 (2012) 701–705. https://doi.org/10.1016/j.ipl.2012.05.003

[7] S. Grüter, Y. Guo and A. Holtkamp, Restricted arc-connectivity of bipartite tournaments, Discrete Appl. Math. 161 (2013) 2008–2013. https://doi.org/10.1016/j.dam.2013.01.028

[8] S. Grüter, Y. Guo and A. Holtkamp, Restricted arc-connectivity in tournaments, Discrete Appl. Math. 161 (2013) 1467–1471. https://doi.org/10.1016/j.dam.2013.02.010

[9] Z. Liu and Z. Zhang, Restricted connectivity of total digraph, Discrete Math. Algorithms Appl. 08 (2016) 1–9. https://doi.org/10.1142/S1793830916500221

[10] S. Lin, Y. Jin and C. Li, 3 -restricted arc connectivity of digraphs, Discrete Math. 340 (2017) 2341–2348. https://doi.org/10.1016/j.disc.2017.05.004

[11] A. Hellwig and L. Volkmann, Maximally edge-connected and vertex-connected graphs and digraphs: A survey, Discrete Math. 308 (2008) 3265–3296. https://doi.org/10.1016/j.disc.2007.06.035

[12] L. Volkmann, Restricted arc-connectivity of digraphs, Inform. Process. Lett. 103 (2007) 234–239. https://doi.org/10.1016/j.ipl.2007.04.004

[13] S.Y. Wang and S.W. Lin, λ ′ -optimal digraphs, Inform. Process. Lett. 108 (2008) 386–389. https://doi.org/10.1016/j.ipl.2008.07.008