1. Digraph analogues for the Nine Dragon Tree Conjecture.
- Author
-
Gao, Hui and Yang, Daqing
- Subjects
- *
LOGICAL prediction , *DRAGONS , *TREES , *INTEGERS - Abstract
The fractional arboricity of a digraph D $D$, denoted by γ(D) $\gamma (D)$, is defined as γ(D)=maxH⊆D,|V(H)|>1|A(H)||V(H)|−1 $\gamma (D)=\mathop{\max }\limits_{H\subseteq D,|V(H)|\gt 1}\frac{|A(H)|}{|V(H)|-1}$. Frank proved that a digraph D $D$ decomposes into k $k$ branchings, if and only if Δ−(D)≤k ${{\rm{\Delta }}}^{-}(D)\le k$ and γ(D)≤k $\gamma (D)\le k$. In this paper, we study digraph analogues for the Nine Dragon Tree Conjecture. We conjecture that, for positive integers k $k$ and d $d$, if D $D$ is a digraph with γ(D)≤k+d−kd+1 $\gamma (D)\le k+\frac{d-k}{d+1}$ and Δ−(D)≤k+1 ${{\rm{\Delta }}}^{-}(D)\le k+1$, then D $D$ decomposes into k+1 $k+1$ branchings B1,...,Bk,Bk+1 ${B}_{1},\ldots ,{B}_{k},{B}_{k+1}$ with Δ+(Bk+1)≤d ${{\rm{\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 γ(D) $\gamma (D)$ given in the conjecture is best possible. We prove our conjecture for the cases d≤k $d\le k$. As more evidence to support our conjecture, we prove that if D $D$ is a digraph with the maximum average degree mad(D)≤2k+2(d−k)d+1 $\,\text{mad}\,(D)\le 2k+\frac{2(d-k)}{d+1}$ and Δ−(D)≤k+1 ${{\rm{\Delta }}}^{-}(D)\le k+1$, then D $D$ decomposes into k+1 $k+1$ pseudo‐branchings C1,...,Ck,Ck+1 ${C}_{1},\ldots ,{C}_{k},{C}_{k+1}$ with Δ+(Ck+1)≤d ${{\rm{\Delta }}}^{+}({C}_{k+1})\le d$. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF