Indexed by:
Abstract:
The maximum average degree of a graph G, denoted by mad(G), is defined as mad(G) = max(H subset of G) 2e(H)/upsilon(H) . Suppose that a is an orientation of G, G(sigma) denotes the oriented graph. It is well-known that for any graph G, there exists an orientation sigma such that Delta(+) (G(sigma)) <= 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. (C) 2015 Elsevier Inc. All rights reserved.
Keyword:
Reprint 's Address:
Version:
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 Discipline: MATHEMATICS;
ESI HC Threshold:86
JCR Journal Grade:1
CAS Journal Grade:2
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: 0
Affiliated Colleges: