A note on the restricted arc connectivity of oriented graphs of girth four

Abstract: Let

D

be a strongly connected digraph. An arc set

S

of

D

is a emph{restricted arc-cut} of

D

if

D - S

has a non-trivial strong component

D_{1}

such that

D - V (D_{1})

contains an arc. The emph{restricted arc-connectivity}

l a m b d a^{'} (D)

of a digraph

D

is the minimum cardinality over all restricted arc-cuts of

D

. A strongly connected digraph

D

is emph{

l a m b d a^{'}

-connected} when

l a m b d a^{'} (D)

exists. This paper presents a family

c a l F

of strong digraphs of girth four that are not

l a m b d a^{'}

-connected and for every strong digraph

D o t i n c a l F

with girth four it follows that it is

l a m b d a^{'}

-connected. Also, an upper and lower bound for

l a m b d a^{'} (D)

are given.

Recommendations

Cites Work

Cited In (2)

This page was built for publication: A note on the restricted arc connectivity of oriented graphs of girth four