Abstract
For a digraph \(D=(V(D), A(D))\), and a set \(S\subseteq V(D)\) with \(r\in S\) and \(|S|\ge 2\), an (S, r)-tree is an out-tree T rooted at r with \(S\subseteq V(T)\). Two (S, r)-trees \(T_1\) and \(T_2\) are said to be arc-disjoint if \(A(T_1)\cap A(T_2)=\emptyset \). Two arc-disjoint (S, r)-trees \(T_1\) and \(T_2\) are said to be internally disjoint if \(V(T_1)\cap V(T_2)=S\). Let \(\kappa _{S,r}(D)\) and \(\lambda _{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
Similarly, the generalized k-arc-strong connectivity of D is defined as
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 and a natural extension of undirected tree connectivity. A digraph \(D=(V(D), A(D))\) is called minimally generalized \((k, \ell )\)-vertex (respectively, arc)-strongly connected if \(\kappa _k(D)\ge \ell \) (respectively, \(\lambda _k(D)\ge \ell \)) but for any arc \(e\in A(D)\), \(\kappa _k(D-e)\le \ell -1\) (respectively, \(\lambda _k(D-e)\le \ell -1\)). In this paper, we study the minimally generalized \((k, \ell )\)-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 \(\ell \).
Similar content being viewed by others
References
Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer, London (2009)
Cheriyan, J., Salavatipour, M.: Hardness and approximation results for packing Steiner trees. Algorithmica 45, 21–43 (2006)
Hager, M.: Pendant tree-connectivity. J. Comb. Theory Ser. B 38, 179–189 (1985)
Halin, R.: A theorem on \(n\)-connected graphs. J. Comb. Theory 7, 150–154 (1969)
Kameda, T.: Note on Halin’s theorem on minimally connected graphs. J. Comb. Theory Ser. B 17, 1–4 (1974)
Li, X., Mao, Y.: Generalized Connectivity of Graphs. Springer, Switzerland (2016)
Li, X., Mao, Y., Sun, Y.: On the generalized (edge-)connectivity of graphs. Australas. J. Comb. 58(2), 304–319 (2014)
Mader, W.: Minimal \(n\)-fach zusammenhängende Digraphen. J. Comb. Theory Ser. B 38(2), 102–117 (1985)
Mader, W.: On vertices of outdegree \(n\) in minimally \(n\)-connected digraphs. J. Graph Theory 39, 129–144 (2002)
Sun, Y., Gutin, G.: Strong subgraph connectivity of digraphs. Graphs Comb. 37, 951–970 (2021)
Sun, Y., Gutin, G., Yeo, A., Zhang, X.: Strong subgraph \(k\)-connectivity. J. Graph Theory 92(1), 5–18 (2019)
Sun, Y., Yeo, A.: Directed Steiner tree packing and directed tree connectivity (2020). ar**v:2005.00849v3 [math.CO]
Sun, Y., Zhou, S.: Tree connectivities of Cayley graphs on Abelian groups with small degrees. Bull. Malays. Math. Sci. Soc. 39(4), 1673–1685 (2016)
Tillson, T.W.: A Hamiltonian decomposition of \(K^*_{2m}\), \(2m \ge 8\). J. Comb. Theory Ser. B 29(1), 68–74 (1980)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Sandi Klavžar.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This research was supported by Yongjiang Talent Introduction Programme of Ningbo and Zhejiang Provincial Natural Science Foundation of China under Grant No. LY20A010013.
Rights and permissions
About this article
Cite this article
Sun, Y. Extremal Results for Directed Tree Connectivity. Bull. Malays. Math. Sci. Soc. 45, 839–850 (2022). https://doi.org/10.1007/s40840-021-01237-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40840-021-01237-1
Keywords
- Directed tree connectivity
- Generalized k-vertex-strong connectivity
- Generalized k-arc-strong connectivity
- Directed Steiner tree packing
- Out-tree
- Out-branching