کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903505 | 1632569 | 2017 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Gallai's conjecture for graphs with treewidth 3
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Gallai conjectured (1966) that the edge-set of a simple graph G with n vertices can be covered by at most (n+1)/2 edge-disjoint paths. Lovász [Lovász, L., On covering of graphs, in: Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968 pp. 231-236.] verified this conjecture for graphs with at most one vertex of even degree, and Pyber [Pyber, L., Covering the edges of a connected graph by paths, J. Combin. Theory Ser. B 66 (1996), pp. 152-159.] verified it for graphs in which every cycle contains a vertex of odd degree. Recently, Bonamy and Perrett verified this Conjecture for graphs with maximum degree at most 5. In this paper, we verify the Conjecture for graphs with treewidth at most 3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 147-152
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 147-152
نویسندگان
Fábio Botler, Maycon Sambinelli,