# 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 [math]s[/math], whose (simultaneous) splitting off does not destroy the *k*-arc-connectivity of *D* in *V*?

## Remarks

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

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

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

The case [math]l=1[/math] is proved in ^{[2]}; see also ^{[3]}.

## References

- ↑ W. Mader,
*Konstruktion aller [math]n[/math]-fach kantenzusammenhängenden Digraphen*, Europ. J. Combinatorics 3 (1982) 63-67, DOI link. - ↑
^{2.0}^{2.1}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 - ↑ 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.