Premium
Digraph analogues for the Nine Dragon Tree Conjecture
Author(s) -
Gao Hui,
Yang Daqing
Publication year - 2023
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22884
Subject(s) - digraph , conjecture , combinatorics , mathematics , bipartite graph , tree (set theory) , discrete mathematics , graph
The fractional arboricity of a digraphD $D$ , denoted byγ ( D )$\gamma (D)$ , is defined asγ ( D ) = max H ⊆ 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 digraphD $D$ decomposes intok $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 integersk $k$ andd $d$ , ifD $D$ is a digraph withγ ( D ) ≤ k + d − k d + 1$\gamma (D)\le k+\frac{d-k}{d+1}$ andΔ − ( D ) ≤ k + 1 ${{\rm{\Delta }}}^{-}(D)\le k+1$ , thenD $D$ decomposes intok + 1 $k+1$ branchingsB 1 , … , B k , B k + 1${B}_{1},\ldots ,{B}_{k},{B}_{k+1}$ withΔ + ( B k + 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 casesd ≤ k $d\le k$ . As more evidence to support our conjecture, we prove that ifD $D$ is a digraph with the maximum average degreemad( D ) ≤ 2 k + 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$ , thenD $D$ decomposes intok + 1 $k+1$ pseudo‐branchingsC 1 , … , C k , C k + 1${C}_{1},\ldots ,{C}_{k},{C}_{k+1}$ withΔ + ( C k + 1 ) ≤ d ${{\rm{\Delta }}}^{+}({C}_{k+1})\le d$ .