کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328421 | 684001 | 2005 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Decomposing toroidal graphs into circuits and edges
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
ErdÅs et al. (Canad. J. Math. 18 (1966) 106-112) conjecture that there exists a constant dce such that every simple graph on n vertices can be decomposed into at most dcen circuits and edges. We consider toroidal graphs, where the graphs can be embedded on the torus, and give a polynomial time algorithm to decompose the edge set of an even toroidal graph on n vertices into at most (n+3)/2 circuits. As a corollary, we get a polynomial time algorithm to decompose the edge set of a toroidal graph (not necessarily even) on n vertices into at most 3(n-1)/2 circuits and edges. This settles the conjecture for toroidal graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 148, Issue 2, 15 May 2005, Pages 147-159
Journal: Discrete Applied Mathematics - Volume 148, Issue 2, 15 May 2005, Pages 147-159
نویسندگان
Baogang Xu, Lusheng Wang,