We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Extremal Results for Directed Tree Connectivity.
- Authors
Sun, Yuefang
- Abstract
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 T 1 and T 2 are said to be arc-disjoint if A (T 1) ∩ A (T 2) = ∅ . Two arc-disjoint (S, r)-trees T 1 and T 2 are said to be internally disjoint if V (T 1) ∩ V (T 2) = 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 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 , ℓ) -vertex (respectively, arc)-strongly connected if κ k (D) ≥ ℓ (respectively, λ k (D) ≥ ℓ ) but for any arc e ∈ A (D) , κ k (D - e) ≤ ℓ - 1 (respectively, λ k (D - e) ≤ ℓ - 1 ). In this paper, we study the minimally generalized (k , ℓ) -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 ℓ .
- Subjects
TREES; GENERALIZATION; MULTICASTING (Computer networks)
- Publication
Bulletin of the Malaysian Mathematical Sciences Society, 2022, Vol 45, Issue 2, p839
- ISSN
0126-6705
- Publication type
Article
- DOI
10.1007/s40840-021-01237-1