Strong Subgraph Connectivity of Digraphs

Abstract

Abstract Let $$D=(V,A)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>D</mml:mi> <mml:mo>=</mml:mo> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>A</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> be a digraph of order n , S a subset of V of size k and $$2\le k\le n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>k</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> . A strong subgraph H of D is called an S - strong subgraph if $$S\subseteq V(H)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>H</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . A pair of S -strong subgraphs $$D_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>D</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> and $$D_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>D</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> are said to be arc-disjoint if $$A(D_1)\cap A(D_2)=\emptyset$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>D</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>∩</mml:mo> <mml:mi>A</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>D</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>∅</mml:mi> </mml:mrow> </mml:math> . A pair of arc-disjoint S -strong subgraphs $$D_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>D</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> and $$D_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>D</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> are said to be internally disjoint if $$V(D_1)\cap V(D_2)=S$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>V</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>D</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>∩</mml:mo> <mml:mi>V</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>D</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>S</mml:mi> </mml:mrow> </mml:math> . Let $$\kappa _S(D)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>κ</mml:mi> <mml:mi>S</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>D</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> (resp. $$\lambda _S(D)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>λ</mml:mi> <mml:mi>S</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>D</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> ) be the maximum number of internally disjoint (resp. arc-disjoint) S -strong subgraphs in D . The strong subgraph k -connectivity is defined as $$\begin{aligned} \kappa _k(D)=\min \{\kappa _S(D)\mid S\subseteq V, |S|=k\}. \end{aligned}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mrow> <mml:msub> <mml:mi>κ</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>D</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mo>min</mml:mo> <mml:mo>{</mml:mo> </mml:mrow> <mml:msub> <mml:mi>κ</mml:mi> <mml:mi>S</mml:mi> </mml:msub> <mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>D</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>∣</mml:mo> <mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mo>|</mml:mo> <mml:mi>S</mml:mi> <mml:mo>|</mml:mo> <mml:mo>=</mml:mo> <mml:mi>k</mml:mi> <mml:mo>}</mml:mo> <mml:mo>.</mml:mo> </mml:mrow> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:math> As a natural counterpart of the strong subgraph k -connectivity, we introduce the concept of strong subgraph k -arc-connectivity which is defined as $$\begin{aligned} \lambda _k(D)=\min \{\lambda _S(D)\mid S\subseteq V(D), |S|=k\}. \end{aligned}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">

Topics & Concepts