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

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
نویسندگان
,