## Abstract

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.).

Original language | English |
---|---|

Journal | Journal of Graph Theory |

Volume | 102 |

Issue number | 1 |

Pages (from-to) | 86-106 |

ISSN | 0364-9024 |

DOIs | |

Publication status | Published - Jan 2023 |

## Keywords

- directed k-linkage
- directed Steiner tree packing
- directed tree connectivity
- Eulerian digraph
- out-tree
- semicomplete digraph
- symmetric digraph