# Incomplete splitting-off in digraphs

Given a digraph D=(V+s,A) which is k-arc-connected in V, what is the maximum number of (disjoint) pairs of arcs, consisting of entering and leaving arcs at $s$, whose (simultaneous) splitting off does not destroy the k-arc-connectivity of D in V?

## Remarks

A theorem of Mader [1] implies that if $\rho(s)=\delta(s)$, then there is a complete splitting off at $s$. It is also easy to see from this result that if $\frac{1}{2}\delta (s) \lt \rho (s) \lt 2 \delta(s),$ then at least one pair of arcs can be split off at $s$.

In [2], Berg, Jackson, and Jordán proposed the following conjecture:

Conjecture: Let $D=(V+s,E)$ be a digraph with $\rho(s)\geq \delta(s)$, and suppose that $D$ is $k$-edge-connected in $V$. Then $D$ does not have a sequence of $l$ splits at $s$ which preserve the $k$-edge-connectivity in $V$ if and only if there is a family ${\mathcal F} = \{R_1,R_2,\ldots,R_r\}$ of subsets of $V$, where $2 \leq r \leq 2l+1$ and $R_i\cup R_j=V$ for $1\leq i\ltj \leq r$, such that $\sum_{i=1}^r\rho(R_i) \leq rk + (r-1)l-q-1,$ where $q=\min\{l, \delta(s,P_1 \cup P_2 \cup \ldots \cup P_r)\}$, and $P_i = V-R_i$ for all $1 \leq i \leq r$.

The case $l=1$ is proved in [2]; see also [3].

## References

1. W. Mader, Konstruktion aller $n$-fach kantenzusammenhängenden Digraphen, Europ. J. Combinatorics 3 (1982) 63-67, DOI link.
2. A. Berg, B. Jackson, T. Jordán, Edge splitting and connectivity augmentation in directed hypergraphs, Discrete Mathematics 273 (2003), 71-84. DOI link. Preliminary version: EGRES Technical Report no. 2001-16
3. A. Frank, Connectivity augmentation problems in network design, in: J. R. Birge, K. G. Murty (eds.): Mathematical Programming: State of the Art. Univ. of Michigan (1994) 34-63. Author link.