کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777356 | 1632751 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Decomposing regular graphs with prescribed girth into paths of given length
ترجمه فارسی عنوان
تجزیه نمودارهای منظم با غلظت تجویز شده به مسیرهای طول داده شده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A Pâ-decomposition of a graph G is a set of pairwise edge-disjoint paths with â edges that cover the edge set of G. In 1957, Kotzig proved that a 3-regular graph admits a P3-decomposition if and only if it contains a perfect matching, and also asked what are the necessary and sufficient conditions for an â-regular graph to admit a Pâ-decomposition, for odd â. Let g, â and m be positive integers with gâ¥3. We prove that, (i) if â is odd and m>2â(ââ2)â(gâ2)â, then every mâ-regular graph with girth at least g that contains an m-factor admits a Pâ-decomposition; (ii) if m>â(ââ2)â(gâ2)â, then every 2mâ-regular graph with girth at least g admits a Pâ-decomposition. Furthermore, we prove that, for graphs with girth at least ââ1, statement (i) holds for every mâ¥1; and observe that, statement (ii) also holds for every mâ¥1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 66, December 2017, Pages 28-36
Journal: European Journal of Combinatorics - Volume 66, December 2017, Pages 28-36
نویسندگان
F. Botler, G.O. Mota, M.T.I. Oshiro, Y. Wakabayashi,