کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656737 1632978 2015 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Decomposing a graph into pseudoforests with one having bounded degree
ترجمه فارسی عنوان
تجزیه یک گراف به شبه جنگل با یک درجه محدود است
کلمات کلیدی
تجزیه گراف، حداکثر درجه متوسط ​​یک گراف، حداکثر خروجی گراف یک گرا، شبه جنگل، نه جنبه درخت درخت اژدها
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 115, November 2015, Pages 72–95
نویسندگان
, , , ,