Article ID Journal Published Year Pages File Type
4656737 Journal of Combinatorial Theory, Series B 2015 24 Pages PDF
Abstract

The maximum average degree of a graph G  , denoted by mad(G)mad(G), is defined as mad(G)=maxH⊆G⁡2e(H)v(H). Suppose that σ is an orientation of G  , GσGσ denotes the oriented graph. It is well-known that for any graph G, there exists an orientation σ   such that Δ+(Gσ)≤kΔ+(Gσ)≤k if and only if mad(G)≤2kmad(G)≤2k.A graph is called a pseudoforest if it contains at most one cycle in each component, is d-bounded if it has maximum degree at most d. In this paper, it is proven that, for any non-negative integers k and d, if G   is a graph with mad(G)≤2k+2dk+d+1, then G   decomposes into k+1k+1 pseudoforests with one being d-bounded. This result in some sense is analogous to the Nine Dragon Tree (NDT) Conjecture, which is a refinement of the famous Nash–Williams Theorem that characterizes the decomposition of a graph into forests. A class of examples is also presented to show the sharpness of our result.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,