Geodesic
Minimally Strong Subgraph (k, ℓ)-Arc-Connected Digraphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 759-770.

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

Let D = (V,A) be a digraph of order n, S a subset of V of size k and 2 ≤ k ≤ n. A subdigraph H of D is called an S-strong subgraph if H is strong and S ⊆ V (H). Two S-strong subgraphs D_1 and D_2 are said to be arc-disjoint if A(D_1) ∩ A(D_2) = ∅. Let λ_S (D) be the maximum number of arc-disjoint S-strong digraphs in D. The strong subgraph k-arc-connectivity is defined as λ_k (D) = min{λ_S (D) | S ⊆ V, |S| = k }. A digraph D = (V, A) is called minimally strong subgraph (k, 𝓁)-arc-connected if λ_k (D) ≥𝓁 but for any arc e ∈ A, λ_k(D − e) ≤𝓁 − 1. Let 𝔊(n, k, 𝓁 ) be the set of all minimally strong subgraph (k, 𝓁 )-arc-connected digraphs with order n. We define G(n, k, 𝓁 ) = max{ |A(D)| | D ∈𝔊 (n, k, 𝓁 ) } and g(n, k, 𝓁 ) = min{ |A(D)| | D ∈𝔊(n, k, 𝓁 ) }. In this paper, we study the minimally strong subgraph (k, 𝓁 )-arc-connected digraphs. We give a characterization of the minimally strong sub-graph (3, n − 2)-arc-connected digraphs, and then give exact values and bounds for the functions g(n, k, 𝓁 ) and G(n, k, 𝓁 ).
Keywords: strong subgraph k -connectivity, strong subgraph k -arc-connectivity, subdigraph packing 
@article{DMGT_2022_42_3_a4,
     author = {Sun, Yuefang and Jin, Zemin},
     title = {Minimally {Strong} {Subgraph} (k, {\ensuremath{\ell})-Arc-Connected} {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {759--770},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a4/}
}
TY  - JOUR
AU  - Sun, Yuefang
AU  - Jin, Zemin
TI  - Minimally Strong Subgraph (k, ℓ)-Arc-Connected Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 759
EP  - 770
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a4/
LA  - en
ID  - DMGT_2022_42_3_a4
ER  - 
%0 Journal Article
%A Sun, Yuefang
%A Jin, Zemin
%T Minimally Strong Subgraph (k, ℓ)-Arc-Connected Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 759-770
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a4/
%G en
%F DMGT_2022_42_3_a4
Sun, Yuefang; Jin, Zemin. Minimally Strong Subgraph (k, ℓ)-Arc-Connected Digraphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 759-770. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a4/

[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd Edition (Springer, London, 2009). https://doi.org/10.1007/978-1-84800-998-1

[2] J. Bang-Jensen and J. Huang, Decomposing locally semicomplete digraphs into strong spanning subdigraphs, J. Combin. Theory Ser. B 102 (2012) 701–714. https://doi.org/10.1016/j.jctb.2011.09.001

[3] J. Bang-Jensen and M. Kriesell, Disjoint sub ( di)graphs in digraphs, Electron. Notes Discrete Math. 34 (2009) 179–183. https://doi.org/10.1016/j.endm.2009.07.030

[4] J. Bang-Jensen and A. Yeo, Decomposing k-arc-strong tournaments into strong spanning subdigraphs, Combinatorica 24 (2004) 331–349. https://doi.org/10.1007/s00493-004-0021-z

[5] J. Bang-Jensen and A. Yeo, Arc-disjoint spanning sub ( di ) graphs in digraphs, Theoret. Comput. Sci. 438 (2012) 48–54. https://doi.org/10.1016/j.tcs.2012.03.003

[6] J.A. Bondy and U.S.R. Murty, Graph Theory, GTM 244 (Springer, Berlin, 2008).

[7] J. Cheriyan and M.R. Salavatipour, Hardness and approximation results for packing Steiner trees, Algorithmica 45 (2006) 21–43. https://doi.org/10.1007/s00453-005-1188-4

[8] M. Hager, Pendant tree-connectivity, J. Combin. Theory Ser. B 38 (1985) 179–189. https://doi.org/10.1016/0095-8956(85)90083-8

[9] X. Li and Y. Mao, Generalized Connectivity of Graphs (Springer, Switzerland, 2016). https://doi.org/10.1007/978-3-319-33828-6

[10] X. Li, Y. Mao and Y. Sun, On the generalized ( edge- ) connectivity of graphs, Australas. J. Combin. 58 (2014) 304–319.

[11] Y. Sun and G. Gutin, Strong subgraph k-arc-connectivity . arXiv:1805.01687v1

[12] Y. Sun and G. Gutin, Strong subgraph connectivity of digraphs: A survey . arXiv:1808.02740v1

[13] Y. Sun, G. Gutin and J. Ai, Arc-disjoint strong spanning subdigraphs in compositions and products of digraphs, Discrete Math. 342 (2019) 2297–2305. https://doi.org/10.1016/j.disc.2019.05.003

[14] Y. Sun, G. Gutin, A. Yeo and X. Zhang, Strong subgraph k-connectivity, J. Graph Theory 92 (2019) 5–18. https://doi.org/10.1002/jgt.22437

[15] T.W. Tillson, A Hamiltonian decomposition of K*2m, 2 m ≥ 8, J. Combin. Theory Ser. B 29 (1980) 68–74. https://doi.org/10.1016/0095-8956(80)90044-1