Strong subgraph k-connectivity bounds

Abstract: Let

D = (V, A)

be a digraph of order

n

,

S

a subset of

V

of size

k

and

2 l e k l e q n

. Strong subgraphs

D_{1}, d o t s, D_{p}

containing

S

are said to be internally disjoint if

V (D_{i}) c a p V (D_{j}) = S

and

A (D_{i}) c a p A (D_{j}) = e m p t y s e t

for all

1 l e i < j l e p

. Let

k a p p a_{S} (D)

be the maximum number of internally disjoint strong digraphs containing

S

in

D

. The strong subgraph

k

-connectivity is defined as

kappa_k(D)=min{kappa_S(D)mid Ssubseteq V, |S|=k}.

A digraph

D = (V, A)

is called minimally strong subgraph

(k, e l l)

-connected if

k a p p a_{k} (D) g e q e l l

but for any arc

e i n A

,

k a p p a_{k} (D - e) l e q e l l - 1

. In this paper, we first give a sharp upper bound for the parameter

k a p p a_{k} (D)

and then study the minimally strong subgraph

(k, e l l)

-connected digraphs.

This page was built for publication: Strong subgraph $k$-connectivity bounds