Incomplete splitting-off in digraphs

From Egres Open
Jump to: navigation, search

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

  1. W. Mader, Konstruktion aller [math]n[/math]-fach kantenzusammenhängenden Digraphen, Europ. J. Combinatorics 3 (1982) 63-67, DOI link.
  2. 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
  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.