Minimally Strong Subgraph (k,ℓ)-Arc-Connected Digraphs

Abstract

Let D = (V,A) be a digraph of order n, S a subset of V of size k and 2 ≤ k ≤ n. A subdigraph H of D is called an S-strong subgraph if H is strong and S ⊆ V (H). Two S-strong subgraphs D1 and D2 are said to be arc-disjoint if A(D1) ∩ A(D2) = ∅. Let λS(D) be the maximum number of arc-disjoint S-strong digraphs in D. The strong subgraph k- arc-connectivity is defined as λk(D) = min{λS(D) | S ⊆ V, |S| = k}. A digraph D = (V,A) is called minimally strong subgraph (k, ℓ)-arc-connected if λk(D) ≥ ℓ but for any arc e ∈ A, λk(D − e) ≤ ℓ − 1. Let 𝔊 (n, k, ℓ) be the set of all minimally strong subgraph (k, ℓ)-arc-connected digraphs with order n. We define G(n, k, ℓ) = max{|A(D)| | D ∈𝔊 (n, k, ℓ)} and g(n, k, ℓ) = min{|A(D)| | D ∈ 𝔊(n, k, ℓ)}.

Keywords

• strong subgraph k-connectivity
• strong subgraph k-arc-connectivity
• subdigraph packing
• 05c20
• 05c35
• 05c40
• 05c70
• 05c75