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