Article in volume
Authors:
Title:
On the optimality of 3-restricted arc connectivity for digraphs and bipartite digraphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 321-332
Received: 2018-10-08 , Revised: 2019-10-05 , Accepted: 2019-10-05 , Available online: 2022-01-20 , https://doi.org/10.7151/dmgt.2259
Abstract:
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^\prime$ with order at least $k$ such that
$D\backslash V(D^\prime)$ contains a connected subdigraph with order at least
$k$. If such a $k$-restricted arc cut exists in $D$, then $D$ is called
$\lambda^k$-connected. For a $\lambda^k$-connected digraph $D$, the
$k$-restricted arc connectivity, denoted by $\lambda^k(D)$, is the minimum
cardinality over all $k$-restricted arc cuts of $D$. It is known that for many
digraphs $\lambda^k(D)\leq\xi^k(D)$, where $\xi^k(D)$ denotes the minimum
$k$-degree of $D$. $D$ is called $\lambda^k$-optimal if $\lambda^k(D)=\xi^k(D)$.
In this paper, we will give some sufficient conditions for digraphs and
bipartite digraphs to be $\lambda^3$-optimal.
Keywords:
restricted arc-connectivity, bipartite digraph, optimality, digraph, network
References:
- 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 - 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 - 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 - C. Balbuena, C. Cera, A. Diánez, P. García-Vázquez and X. Marcote, Sufficient conditions for $\lambda^\prime$-optimality of graphs with small conditional diameter, Inform. Process. Lett. 95 (2005) 429–434.
https://doi.org/10.1016/j.ipl.2005.05.006 - 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 - X. Chen, J. Liu and J. Meng, $\lambda^\prime$-optimality of bipartite bigraphs, Inform. Process. Lett. 112 (2012) 701–705.
https://doi.org/10.1016/j.ipl.2012.05.003 - 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 - 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 - Z. Liu and Z. Zhang, Restricted connectivity of total digraph, Discrete Math. Algorithms Appl. 08 (2016) 1–9.
https://doi.org/10.1142/S1793830916500221 - 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 - 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 - L. Volkmann, Restricted arc-connectivity of digraphs, Inform. Process. Lett. 103 (2007) 234–239.
https://doi.org/10.1016/j.ipl.2007.04.004 - S.Y. Wang and S.W. Lin, $\lambda^\prime$-optimal digraphs, Inform. Process. Lett. 108 (2008) 386–389.
https://doi.org/10.1016/j.ipl.2008.07.008
Close