کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427965 686581 2010 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Decomposition of sparse graphs into two forests, one having bounded maximum degree
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Decomposition of sparse graphs into two forests, one having bounded maximum degree
چکیده انگلیسی

Let G be a graph. The maximum average degree of G, written Mad(G), is the largest average degree among the subgraphs of G. It was proved in Montassier et al. (2010) [11] that, for any integer k⩾0, every simple graph with maximum average degree less than admits an edge-partition into a forest and a subgraph with maximum degree at most k; furthermore, when k⩽3 both subgraphs can be required to be forests. In this note, we extend this result proving that, for k=4,5, every simple graph with maximum average degree less than mk admits an edge-partition into two forests, one having maximum degree at most k (i.e. every graph with maximum average degree less than (resp. ) admits an edge-partition into two forests, one having maximum degree at most 4 (resp. 5)).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 110, Issue 20, 30 September 2010, Pages 913-916