Pushing Vertices and the Strong Connectivity of Bipartite Tournaments
推点与二部竞赛图的强连通性

Let $D$ be a digraph and $S$ a subset of $V(D)$. {Pushing $S$} in $D$means reversing the orientation of all arcs with exactly one end in $S$.Klostermeyer proved that it is $NP-$complete to decide if a givendigraph $D$ can be made strongly connected by pushing vertices. In this paper, we show that, for any bipartite tournament $D$ with the bipartition$(X,Y)$ of $V(D)$, if $3\leq |X|\leq |Y|\leq 2^{|X|-1}-1$, then $D$ can be made strongly connected by pushing vertices, and this result is best possible.