کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419236 683758 2016 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Induced 2-regular subgraphs in kk-chordal cubic graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Induced 2-regular subgraphs in kk-chordal cubic graphs
چکیده انگلیسی

We show that a cubic graph GG of order nn has an induced 2-regular subgraph of order at least
• n−24−4k, if GG has no induced cycle of length more than kk,
• 5n+68, if GG has no induced cycle of length more than 4, and n>6n>6, and
• (14+ϵ)n, if the independence number of GG is at most (38−ϵ)n. To show the second result we give a precise structural description of cubic 4-chordal graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 205, 31 May 2016, Pages 73–79
نویسندگان
, , , ,