2022/11/08 by Yuefang Sun, Sun, Yuefang
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2211.04025
openalex publication_date 2022/11/08 · 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, a directed (S, r)-Steiner path or, simply, an (S, r)-path is a directed path P started at r with S⊆ V(P). Two (S, r)-paths are said to be arc-disjoint if they have no common arc. Two arc-disjoint (S, r)-paths are said to be internally disjoint if the set of common vertices of them is exactly S. Let κpS,r(D) (resp. λpS,r(D)) be the maximum number of internally disjoint (resp. arc-disjoint) (S, r)-paths in D. The directed path k-connectivity of D is defined as κpk(D)= min \κpS,r(D)| S⊆ V(D), |S|=k, r∈ S\. Similarly, the directed path k-arc-connectivity of D is defined as λpk(D)= min \λpS,r(D)| S⊆ V(D), |S|=k, r∈ S\. The directed path k-connectivity and directed path k-arc-connectivity are also called directed path connectivity which extends the path connectivity on undirected graphs to directed graphs and could be seen as a generalization of classical connectivity of digraphs. In this paper, we obtain complexity results for κpS,r(D) on Eulerian digraphs and symmetric digraphs, and λpS,r(D) on general digraphs. We also give bounds for the parameters κpk(D) and λpk(D).