2020/12/12 by Yuefang Sun, Sun, Yuefang
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2012.06698
openalex publication_date 2020/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a digraph D=(V(D), A(D)), and a set S⊆ V(D) with r∈ S and |S|≥ 2, an (S, r)-tree is an out-tree T rooted at r with S⊆ V(T). Two (S, r)-trees T1 and T2 are said to be arc-disjoint if A(T1)∩ A(T2)=∅. Two arc-disjoint (S, r)-trees T1 and T2 are said to be internally disjoint if V(T1)∩ V(T2)=S. Let κS,r(D) and λS,r(D) be the maximum number of internally disjoint and arc-disjoint (S, r)-trees in D, respectively. The generalized k-vertex-strong connectivity of D is defined as κk(D)= min \κS,r(D)| S⊂ V(D), |S|=k, r∈ S\. Similarly, the generalized k-arc-strong connectivity of D is defined as λk(D)= min \λS,r(D)| S⊂ V(D), |S|=k, r∈ S\. The generalized k-vertex-strong connectivity and generalized k-arc-strong connectivity are also called directed tree connectivity which could be seen as a generalization of classical connectivity of digraphs. A digraph D=(V(D), A(D)) is called minimally generalized (k, ℓ)-vertex (respectively, arc)-strongly connected if κk(D)≥ ℓ (respectively, λk(D)≥ ℓ) but for any arc e∈ A(D), κk(D-e)≤ ℓ-1 (respectively, λk(D-e)≤ ℓ-1). In this paper, we study the minimally generalized (k, ℓ)-vertex (respectively, arc)-strongly connected digraphs. We compute the minimum and maximum sizes of these digraphs, and give characterizations of such digraphs for some pairs of k and ℓ.