کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9512206 | 1342470 | 2005 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A bound on the total size of a cut cover
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We discuss several results for cycle covers and the corresponding results for cut covers. Our main result is that every connected graph on n vertices and e edges has a cut cover of total size at most 2e-n+1 with equality precisely when every block of the graph is an odd cycle or a complete graph (other than K4 or K8). This corresponds to the result of Fan [J. Combin. Theory Ser. B 74 (1998) 353-367] that every graph without cut-edges has a cycle cover of total size at most e+n-1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 296, Issue 1, 28 June 2005, Pages 121-128
Journal: Discrete Mathematics - Volume 296, Issue 1, 28 June 2005, Pages 121-128
نویسندگان
André Kündgen, Megan Spangler,