Digraph analogues for the Nine Dragon Tree Conjecture

Abstract

The fractional arboricity of a digraph $D$, denoted by $\gamma (D)$, is defined as $\gamma (D)={\max }_{H\subseteq D,|V(H)|>1}\frac{|A(H)|}{|V(H)|-1}$. Frank in [Covering branching, Acta Scientiarum Mathematicarum (Szeged) 41 (1979), 77-81] proved that a digraph $D$ decomposes into $k$ branchings, if and only if ${\Delta }^{-}(D)\le k$ and $\gamma (D)\le k$. In this paper, we study digraph analogues for the Nine Dragon Tree Conjecture. We conjecture that, for positive integers $k$ and $d$, if $D$ is a digraph with $\gamma (D)\le k+\frac{d-k}{d+1}$ and ${\Delta }^{-}(D)\le k+1$, then $D$ decomposes into $k+1$ branchings $B_1,\dots ,B_k,B_{k+1}$ with ${\Delta }^{+}(B_{k+1})\le d$. This conjecture, if true, is a refinement of Frank's characterization. A series of acyclic bipartite digraphs is also presented to show the bound of $\gamma (D)$ given in the conjecture is best possible. We prove our conjecture for the cases $d\le k$. As more evidence to support our conjecture, we prove that if $D$ is a digraph with the maximum average degree $mad(D)$ $\le$ $2k+\frac{2(d-k)}{d+1}$ and ${\Delta }^{-}(D)\le k+1$, then $D$ decomposes into $k+1$ pseudo-branchings $C_1,\dots ,C_k,C_{k+1}$ with ${\Delta }^{+}(C_{k+1})\le d$.