Article in press
Authors:
Title:
On the restricted arc-connectivity of oriented graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-02-25 , Revised: 2024-10-19 , Accepted: 2024-10-19 , Available online: 2024-11-15 , https://doi.org/10.7151/dmgt.2569
Abstract:
For a strong digraph D, the restricted arc-connectivity $\lambda'(D)$ is defined
as the minimum cardinality over all restricted arc-cuts $S$ satisfying that
$D$$-$$S$ has a non-trivial strong component $D_1$ such that $D-V(D_1)$ contains
an arc. In this paper, we prove that a strong oriented black graph
$D$ with diam$(D)\leqslant 2l_2-2$ is $\lambda'$-optimal if $\delta(D)
\geqslant 2$ and $D$ is super-$\lambda'$ if $\delta(D)\geqslant 3$, where $l_2$
is a parameter related with path lengths of $D$.
Keywords:
oriented graph, line digraph, diameter, $\lambda'$-optimal, super-$\lambda'$
References:
- M. Aigner, On the linegraph of a directed graph, Math. Z. 102 (1967) 56–61.
https://doi.org/10.1007/BF01110285 - 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, On the super-restricted arc-connectivity of $s$-geodetic digraphs, Networks 61 (2013) 20–28.
https://doi.org/10.1002/net.21462 - 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 - 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'$-optimality of bipartite digraphs, Inform. Process. Lett. 112 (2012) 701–705.
https://doi.org/10.1016/j.ipl.2012.05.003 - A.H. Esfahanian and S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988) 195–199.
https://doi.org/10.1016/0020-0190(88)90025-7 - J. Fàbrega, M.A. Foil and J.L.A. Yebra, Connectivity and reliable routing algorithms in line digraphs, in: Proceedings of the III IAESTED International Symposium on Applied Informatics (Grindelwald, Switzerland, 1985) 45–50.
- D. González-Moreno and R. Hernández Ortiz, A note on the restricted arc connectivity of oriented graphs of girth four, Australas. J. Combin. 70 (2018) 340–348.
- S. Grüter, Y. Guo, A. Holtkamp and E. Ulmer, Restricted arc-connectivity in tournaments, Discrete Appl. Math. 161 (2013) 1467–1471.
https://doi.org/10.1016/j.dam.2013.02.010 - 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. Lin and D. Ding, Minimum degree conditions for oriented graphs to be super-$\lambda'$, Henan Science 34 (2016) 157–160.
- S. Lin and N. Fan, Restricted arc connectivity of unidirectional hypercubes and unidirectional folded hypercubes, Taiwanese J. Math. 23 (2019) 529–543.
https://doi.org/10.11650/tjm/180808 - S. Lin, Y. Jin and C. Li, Cartesian product digraphs with optimal restricted arc connectivity, Inform. Process. Lett. 134 (2018) 72–75.
https://doi.org/10.1016/j.ipl.2018.02.014 - J. Liu, L. Sun and J. Meng, A line digraph of a complete bipartite digraph, Appl. Math. Lett. 22 (2009) 544–547.
https://doi.org/10.1016/j.aml.2008.04.013 - D. Meierling, L. Volkmann and S. Winzen, Restricted arc-connectivity of generalized tournaments, Australas. J. Combin. 40 (2008) 269–278.
- M.A. Foil, J.L.A. Yebra and I.A. de Miquel, Line digraph iterations and the $(d,k)$ digraph problem, IEEE Trans. Comput. C-33 (1984) 400–403.
https://doi.org/10.1109/TC.1984.1676455 - S.M. Reddy, J.G. Kuhl, S.H. Hosseini and H. Lee, On digraphs with minimum diameter and maximum connectivity, in: Proccedings of Allerton Conf. on Communications, Control and Computers, Illinois (1982) 1018–1026.
- 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. Wang and S. Lin, $\lambda'$-optimal digraphs, Inform. Process. Lett. 108 (2008) 386–389.
https://doi.org/10.1016/j.ipl.2008.07.008 - X. Zhao, Q. Deng and Z. Wang, Restricted arc-connectivity of unidirectional star graphs, Discrete Appl. Math. 345 (2024) 207–214.
https://doi.org/10.1016/j.dam.2023.12.010
Close