Digraph analogues for the Nine Dragon Tree Conjecture

DOI10.1002/JGT.22884zbMATH Open1522.05161arXiv2201.10791WikidataQ123247855 ScholiaQ123247855MaRDI QIDQ6046686FDOQ6046686

Authors: Hui Gao, Daqing Yang 

Publication date: 6 October 2023

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

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$.

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

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

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)

Cites Work

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

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)