Source author record

Daqing Yang

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

5works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Digraph analogues for the Nine Dragon Tree Conjecture

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

preprint2020arXiv

Packing branchings under cardinality constraints on their root sets

Edmonds' fundamental theorem on arborescences characterizes the existence of $k$ pairwise arc-disjoint spanning arborescences with prescribed root sets in a digraph. In this paper, we study the problem of packing branchings in digraphs under cardinality constraints on their root sets by arborescence augmentation. Let $D=(V+x,A)$ be a digraph, $\mathcal{P}=$ $\{I_{1}, \ldots, I_{l} \}$ be a partition of $[k]$ , $c_{1}, \ldots, c_{l}, c'_{1}, \ldots, c'_{l}$ be nonnegative integers such that $c_α \leq c'_α$ for $α\in [l]$ , $F_{1}, \ldots, F_{k}$ be $k$ arc-disjoint $x$ -arborescences in $D$ such that $\sum_{i \in I_α}d_{F_{i}}^{+}(x)$ $\leq c'_α$ for $α\in [l]$ . We give a characterization on when $F_{1}, \ldots, F_{k}$ can be completed to arc-disjoint spanning $x$ -arborescences $F^{*}_{1}, \ldots, F^{*}_{k}$ such that for any $α\in [l]$ , $c_α \leq \sum_{i \in I_α}d^{+}_{F^{*}_{i}}(x)$ $\leq c'_α$ .

preprint2020arXiv

Packing of maximal independent mixed arborescences

Király in [On maximal independent arborescence packing, SIAM J. Discrete. Math. 30 (4) (2016), 2107-2114] solved the following packing problem: Given a digraph $D = (V, A)$ , a matroid $M$ on a set $S = \{s_{1}, \ldots,s_{k} \}$ along with a map $π: S \rightarrow V$ , find $k$ arc-disjoint maximal arborescences $T_{1}, \ldots ,T_{k}$ with roots $π(s_{1}), \ldots ,π(s_{k})$ , such that, for any $v \in V$ , the set $\{s_{i} : v \in V(T_{i})\}$ is independent and its rank reaches the theoretical maximum. In this paper, we give a new characterization for packing of maximal independent mixed arborescences under matroid constraints. This new characterization is simplified to the form of finding a supermodular function that should be covered by an orientation of each strong component of a matroid-based rooted mixed graph. Our proofs come along with a polynomial-time algorithm. Note that our new characterization extends Király's result to mixed graphs, this answers a question that has already attracted some attentions.

preprint2020arXiv

Packing of spanning mixed arborescences

In this paper, we characterize a mixed graph $F$ which contains $k$ edge and arc disjoint spanning mixed arborescences $F_{1}, \ldots, F_{k}$ , such that for each $v \in V(F)$ , the cardinality of $\{i \in [k]: v \text{ is the root of } F_{i}\}$ lies in some prescribed interval. This generalizes both Nash-Williams and Tutte's theorem on spanning tree packing for undirected graphs and the previous characterization on digraphs which was given by Cai [in: Arc-disjoint arborescences of digraphs, J. Graph Theory 7(2) (1983), 235-240] and Frank [in: On disjoint trees and arborescences, Algebraic Methods in Graph Theory, Colloquia Mathematica Soc. J. Bolyai, Vol. 25 (North-Holland, Amsterdam) (1978), 159-169].

preprint2019arXiv

On coloring numbers of graph powers

The weak $r$ -coloring numbers $wcol_r(G)$ of a graph $G$ were introduced by the first two authors as a generalization of the usual coloring number $col(G)$ , and have since found interesting theoretical and algorithmic applications. This has motivated researchers to establish strong bounds on these parameters for various classes of graphs. Let $G^p$ denote the $p$ -th power of $G$ . We show that, all integers $p >0$ and $Δ\ge 3$ and graphs $G$ with $Δ(G) \leq Δ$ satisfy $col(G^p) \in O(p \cdot wcol_{\lceil p/2\rceil}(G)(Δ-1)^{\lfloor p/2\rfloor})$ ; for fixed tree width or fixed genus the ratio between this upper bound and worst case lower bounds is polynomial in $p$ . For the square of graphs $G$ , we also show that, if the maximum average degree $2k-2 < mad(G) \leq 2k$ , then $col(G^2) \leq (2k-1)Δ(G)+2k+1$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Daqing Yang

Research overview

Is this your work?

5 publications

Digraph analogues for the Nine Dragon Tree Conjecture

Packing branchings under cardinality constraints on their root sets

Packing of maximal independent mixed arborescences

Packing of spanning mixed arborescences

On coloring numbers of graph powers

See the researcher in context

Building this map preview