کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6424132 | 1632769 | 2015 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Tuza's Conjecture for graphs with maximum average degree less than 7
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Tuza's Conjecture states that if a graph G does not contain more than k edge-disjoint triangles, then some set of at most 2k edges meets all triangles of G. We prove Tuza's Conjecture for all graphs G having no subgraph with average degree at least 7. As a key tool in the proof, we introduce a notion of reducible sets for Tuza's Conjecture; these are substructures which cannot occur in a minimal counterexample to Tuza's Conjecture. We also introduce weak König-Egerváry graphs, a generalization of the well-studied König-Egerváry graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 49, October 2015, Pages 134-152
Journal: European Journal of Combinatorics - Volume 49, October 2015, Pages 134-152
نویسندگان
Gregory J. Puleo,