We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Strong Subgraph Connectivity of Digraphs.
- Authors
Sun, Yuefang; Gutin, Gregory
- Abstract
Let D = (V , A) be a digraph of order n, S a subset of V of size k and 2 ≤ k ≤ n . A strong subgraph H of D is called an S-strong subgraph if S ⊆ V (H) . A pair of S-strong subgraphs D 1 and D 2 are said to be arc-disjoint if A (D 1) ∩ A (D 2) = ∅ . A pair of arc-disjoint S-strong subgraphs D 1 and D 2 are said to be internally disjoint if V (D 1) ∩ V (D 2) = S . Let κ S (D) (resp. λ S (D) ) be the maximum number of internally disjoint (resp. arc-disjoint) S-strong subgraphs in D. The strong subgraphk-connectivity is defined as κ k (D) = min { κ S (D) ∣ S ⊆ V , | S | = k }. As a natural counterpart of the strong subgraph k-connectivity, we introduce the concept of strong subgraphk-arc-connectivity which is defined as λ k (D) = min { λ S (D) ∣ S ⊆ V (D) , | S | = k }. A digraph D = (V , A) is called minimally strong subgraph (k , ℓ) -(arc-)connected if κ k (D) ≥ ℓ (resp. λ k (D) ≥ ℓ ) but for any arc e ∈ A , κ k (D - e) ≤ ℓ - 1 (resp. λ k (D - e) ≤ ℓ - 1 ). In this paper, we first give complexity results for λ k (D) , then obtain some sharp bounds for the parameters κ k (D) and λ k (D) . Finally, minimally strong subgraph (k , ℓ) -connected digraphs and minimally strong subgraph (k , ℓ) -arc-connected digraphs are studied.
- Subjects
SUBGRAPHS
- Publication
Graphs & Combinatorics, 2021, Vol 37, Issue 3, p951
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-021-02294-w