Digraph analogues for the Nine Dragon Tree Conjecture

DOI10.1002/JGT.22884MaRDI QIDQ6046686zbMATH OpenWikidataFDO

Authors Hui Gao, Daqing Yang

Publication date 6 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.10791

zbMATH Keywords

branchingfractional arboricitymaximum average degreenine dragon tree conjecturepseudo-branching

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Combinatorial aspects of matroids and geometric lattices (05B35) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The fractional arboricity of a digraph $D$, denoted by $gamma(D)$, is defined as $gamma(D)=ma{x}_{HsubseteqD,|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 $Delt{a}^{-}(D)leqk$ and $gamma(D)leqk$. 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)leqk+fracd-kd+1$ and $Delt{a}^{-}(D)leqk+1$, then $D$ decomposes into $k+1$ branchings $B_1,ldots,B_k,B_{k+1}$ with $Delt{a}^{+}(B_{k+1})leqd$. 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 $dleqk$. As more evidence to support our conjecture, we prove that if $D$ is a digraph with the maximum average degree $mad(D)$ $leq$ $2k+frac2(d-k)d+1$ and $Delt{a}^{-}(D)leqk+1$, then $D$ decomposes into $k+1$ pseudo-branchings $C_1,ldots,C_k,C_{k+1}$ with $Delt{a}^{+}(C_{k+1})leqd$.

Recommendations

• Decomposing a graph into forests: the nine dragon tree conjecture is true
• Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)
• The pseudoforest analogue for the strong nine dragon tree conjecture is true
• Decomposing a graph into forests and a matching
• Decomposition of sparse graphs into forests and a graph with bounded degree

Cites work

• scientific article; zbMATH DE number 3659627 (Why is no real title available?)
• Decomposing a graph into forests
• Decomposing a graph into forests and a matching
• Decomposing a graph into forests: the nine dragon tree conjecture is true
• Decomposing a graph into pseudoforests with one having bounded degree
• Decomposition of Finite Graphs Into Forests
• Decomposition of sparse graphs into forests and a graph with bounded degree
• Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)
• Extensions of matroid covering and packing
• Fractional arboricity, strength, and principal partitions in graphs and matroids
• Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity)
• On the degrees of the vertices of a directed graph
• The pseudoforest analogue for the strong nine dragon tree conjecture is true

Cited in

(2)

• Decomposing a graph into forests: the nine dragon tree conjecture is true
• The pseudoforest analogue for the strong nine dragon tree conjecture is true

This page was built for publication: Digraph analogues for the Nine Dragon Tree Conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046686)