Abstrakt
For a digraph (Formula presented.), and a set (Formula presented.) with (Formula presented.) and (Formula presented.), an (Formula presented.) -tree is an out-tree (Formula presented.) rooted at (Formula presented.) with (Formula presented.). Two (Formula presented.) -trees (Formula presented.) and (Formula presented.) are said to be arc-disjoint if (Formula presented.). Two arc-disjoint (Formula presented.) -trees (Formula presented.) and (Formula presented.) are said to be internally disjoint if (Formula presented.). Let (Formula presented.) and (Formula presented.) be the maximum number of internally disjoint and arc-disjoint (Formula presented.) -trees in (Formula presented.), respectively. The generalized (Formula presented.) -vertex-strong connectivity of (Formula presented.) is defined as (Formula presented.) Similarly, the generalized (Formula presented.) -arc-strong connectivity of (Formula presented.) is defined as (Formula presented.) The generalized (Formula presented.) -vertex-strong connectivity and generalized (Formula presented.) -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 (Formula presented.) and (Formula presented.) 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 equalities for the two parameters (Formula presented.) and (Formula presented.).
| Originalsprog | Engelsk |
|---|---|
| Tidsskrift | Journal of Graph Theory |
| ISSN | 0364-9024 |
| DOI | |
| Status | E-pub ahead of print - 21. jun. 2022 |
Bibliografisk note
Funding Information:We are thankful to Professor Gregory Gutin for discussions on the concept of directed tree connectivity when Yuefang Sun visited Royal Holloway University of London, and Professor Magnus Wahlström for discussions on the complexity of linkage problem for Eulerian digraphs. Yuefang Sun was supported by Zhejiang Provincial Natural Science Foundation under grant number LY20A010013 and Yongjiang Talent Introduction Programme of Ningbo under grant number 2021B‐011‐G, and Anders Yeo was supported by the Independent Research Fund Denmark under grant number DFF 7014‐00037B.
Publisher Copyright:
© 2022 Wiley Periodicals LLC.