کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776800 | 1413642 | 2017 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On line graphs of subcubic triangle-free graphs
ترجمه فارسی عنوان
نمودارهای خطی از نمودارهای آزاد مثلث زیرمجموعه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Line graphs constitute a rich and well-studied class of graphs. In this paper, we focus on three different topics related to line graphs of subcubic triangle-free graphs. First, we show that any such graph G has an independent set of size at least 3|V(G)|â10, the bound being sharp. As an immediate consequence, we have that any subcubic triangle-free graph G, with ni vertices of degree i, has a matching of size at least 3n1â20+3n2â10+9n3â20. Then we provide several approximate min-max theorems relating cycle-transversals and cycle-packings of line graphs of subcubic triangle-free graphs. This enables us to prove Jones' Conjecture for claw-free graphs with maximum degree 4. Finally, we concentrate on the computational complexity of Feedback Vertex Set, Hamiltonian Cycle and Hamiltonian Path for subclasses of line graphs of subcubic triangle-free graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 6, June 2017, Pages 1210-1226
Journal: Discrete Mathematics - Volume 340, Issue 6, June 2017, Pages 1210-1226
نویسندگان
Andrea Munaro,