Improved upper bound on the Frank number of 3-edge-connected graphs

Abstract: In an orientation

O

of the graph

G

, an arc

e

is deletable if and only if

O - e

is strongly connected. For a

3

-edge-connected graph

G

, the Frank number is the minimum

k

for which

G

admits

k

strongly connected orientations such that for every edge

e

of

G

the corresponding arc is deletable in at least one of the

k

orientations. H"orsch and Szigeti conjectured the Frank number is at most

3

for every

3

-edge-connected graph

G

. We prove an upper bound of

5

, which improves the previous bound of

7

.

Cites Work

This page was built for publication: Improved upper bound on the Frank number of 3-edge-connected graphs