On the acyclic disconnection and the girth

Abstract

The acyclic disconnection,−→ω (D), of a digraph D is the maximum number of connected components of the underlying graph of D − A(D∗), where D∗ is an acyclic subdigraph of D. We prove that −→ω (D) ≥ g − 1 for every strongly connected digraph with girth g ≥ 4, and we show that−→ω (D) = g −1 if and only if D ∼= Cg for g ≥ 5. We also characterize the digraphs that satisfy −→ω (D) = g − 1, for g = 4 in certain classes of digraphs. Finally, we define a family of bipartite tournaments based on projective planes and we prove that their acyclic disconnection is equal to 3. Then, these bipartite tournaments are counterexamples of the conjecture −→ω (T ) = 3 if and only if T ∼= −→C 4 posed for bipartite tournaments by Figueroa et al. (2012).