论文标题
九龙树的挖掘类似物猜想
Digraph analogues for the Nine Dragon Tree Conjecture
论文作者
论文摘要
Digraph $ d $的分数（由$γ（d）$表示）定义为$γ（d）= \ max_ {h \ subseteq d，| v（h）| > 1} \ frac {| a（h）|} {| v（h）| -1} $。弗兰克（Frank）在[覆盖分支，Acta Scientiarum Mathematicarum（Szeged）41（1979），77-81]证明，Digraph $ d $分解为$ k $分支，并且仅当$Δ^{ - } { - }（d）\ leq k $ and $ uq k $和$γ（d）\ d）\ d）\ leq k $。 在本文中，我们研究了九龙树猜想的挖掘类似物。我们推测，对于积极的整数$ k $和$ d $，如果$ d $是$γ（d）\ leq k + \ frac {d-k} {d + 1} $和$Δ^{ - } { - } { - }（d）\ leq k + 1 $，然后$ d $ d $ d $ k + 1 $ b _ { b_ {k}，b_ {k+1} $，带有$δ^{+}（b_ {k+1}）\ leq d $。这种猜想是对弗兰克的描述的改进。还提出了一系列的无环二分动物，以显示猜想中给出的$γ（d）$的结合。 我们证明了$ d \ leq k $的猜想。作为支持我们猜想的更多证据，我们证明，如果$ d $是挖掘的，最高平均度$ mad（d）$ $ \ $ \ $ \ $ \ $ 2k + \ frac + \ frac {2（d-k）} {d + 1} $ and $δ^{ - }（ - }（d）（d）\ leq k + 1 $，然后$ d $ $ d $ psse $ k + k + 1 $ cse { \ ldots，c_ {k}，c_ {k+1} $，带有$δ^{+}（c_ {k+1}）\ leq d $。
The fractional arboricity of a digraph $D$, denoted by $γ(D)$, is defined as $γ(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 $Δ^{-}(D) \leq k$ and $γ(D) \leq 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 $γ(D) \leq k + \frac{d-k}{d+1}$ and $Δ^{-}(D) \leq k+1$, then $D$ decomposes into $k + 1$ branchings $B_{1}, \ldots, B_{k}, B_{k+1}$ with $Δ^{+}(B_{k+1}) \leq 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)$ given in the conjecture is best possible. We prove our conjecture for the cases $d \leq k$. As more evidence to support our conjecture, we prove that if $D$ is a digraph with the maximum average degree $mad(D)$ $\leq$ $2k + \frac{2(d-k)}{d+1}$ and $Δ^{-}(D) \leq k+1$, then $D$ decomposes into $k + 1$ pseudo-branchings $C_{1}, \ldots, C_{k}, C_{k+1}$ with $Δ^{+}(C_{k+1}) \leq d$.
