کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650000 1342471 2008 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Disjoint chorded cycles in graphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Disjoint chorded cycles in graphs
چکیده انگلیسی

We propose the following conjecture to generalize results of Pósa and of Corrádi and Hajnal. Let r,sr,s be nonnegative integers and let GG be a graph with |V(G)|≥3r+4s|V(G)|≥3r+4s and minimal degree δ(G)≥2r+3sδ(G)≥2r+3s. Then GG contains a collection of r+sr+s vertex disjoint cycles, ss of them with a chord. We prove the conjecture for r=0,s=2r=0,s=2 and for s=1s=1. The corresponding extremal problem, to find the minimum number of edges in a graph on nn vertices ensuring the existence of two vertex disjoint chorded cycles, is also settled.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 23, 6 December 2008, Pages 5886–5890
نویسندگان
, , ,