paper

Bipartitions with prescribed order of highly connected digraphs

arXiv:2402.16593

Abstract

A digraph is strongly connected if it has a directed path from $x$ to $y$ for every ordered pair of distinct vertices $x, y$ and it is strongly $k$ -connected if it has at least $k + 1$ vertices and remains strongly connected when we delete any set of at most $k - 1$ vertices. For a digraph $D$ , we use $I^´ (D)$ to denote $v \in V (D) min ∣ N_{D}^{+} (v) \cup N_{D}^{-} (v) ∣$ . In this paper, we show the following result. Let $k, l, n, n_{1}, n_{2} \in N$ with $n_{1} + n_{2} \leq n$ and $n_{1}, n_{2} \geq n /20$ . Suppose that $D$ is a strongly $1 0^{7} k (k + l)^{2} lo g (2 k l$ )-connected digraph of order $n$ with $I^´ (D) \geq n - l$ . Then there exist two disjoint subsets $V_{1}, V_{2} \in V (D)$ with $∣ V_{1} ∣ = n_{1}$ and $∣ V_{2} ∣ = n_{2}$ such that each of $D [V_{1}]$ , $D [V_{2}]$ , and $D [V_{1}, V_{2}]$ is strongly $k$ -connected. In particular, $V_{1}$ and $V_{2}$ form a partition of $V (D)$ when $n_{1} + n_{2} = n$ . This result improves the earlier result of Kim, KÃ¼hn, and Osthus [SIAM J. Discrete Math. 30 (2016) 895--911].

23 pages