Indexed by:
Abstract:
The maximum average degree of a graph G, denoted by mad(G), is defined as mad(G)=maxH⊆G2e(H)/v(H). Suppose that σ is an orientation of G, Gσ denotes the oriented graph. It is well-known that for any graph G, there exists an orientation σ such that Δ+(Gσ)≤k if and only if mad(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+2d/k+d+1, then G decomposes into k+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. © 2015 Elsevier Inc.
Keyword:
Reprint 's Address:
Email:
Source :
Journal of Combinatorial Theory. Series B
ISSN: 0095-8956
Year: 2015
Volume: 115
Page: 72-95
1 . 0 9 4
JCR@2015
1 . 2 0 0
JCR@2023
ESI HC Threshold:86
JCR Journal Grade:1
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count: 10
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 5
Affiliated Colleges: