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/