کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903846 1632962 2018 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Decomposing a graph into forests and a matching
ترجمه فارسی عنوان
تجزیه یک گراف به جنگل و تطبیق
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The fractional arboricity of a graph G, denoted by γf(G), is defined as γf(G)=maxH⊆G,v(H)>1⁡e(H)v(H)−1. The famous Nash-Williams' Theorem states that a graph G can be partitioned into at most k forests if and only if γf(G)≤k. A graph is d-bounded if it has maximum degree at most d. The Nine Dragon Tree (NDT) Conjecture [posed by Montassier, Ossona de Mendez, Raspaud, and Zhu, at [11]] asserts that if γf(G)≤k+dk+d+1, then G decomposes into k+1 forests with one being d-bounded. In this paper, it is proven that the Nine Dragon Tree Conjecture is true for all the cases in which d=1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 131, July 2018, Pages 40-54
نویسندگان
,