2020/05/02 by Yuefang Sun, Sun, Yuefang, Anders Yeo +1 · 1 citation
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.2005.00849
openalex publication_date 2020/05/02 · 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 extends the well-established tree connectivity on undirected graphs to directed graphs and could be seen as a generalization of classical connectivity of digraphs. In this paper, we completely determine the complexity for both κS, r(D) and λS, r(D) on general digraphs, symmetric digraphs and Eulerian digraphs. In particular, among our results, we prove and use the NP-completeness of 2-linkage problem restricted to Eulerian digraphs. We also give sharp bounds and characterizations for the two parameters κk(D) and λk(D).