کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903505 1632569 2017 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Gallai's conjecture for graphs with treewidth 3
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Gallai's conjecture for graphs with treewidth 3
چکیده انگلیسی
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
نویسندگان
, ,