کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651078 1632445 2007 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A Chvátal–Erdős type condition for pancyclability
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A Chvátal–Erdős type condition for pancyclability
چکیده انگلیسی

Let GG be a graph and SS a subset of V(G)V(G). Let α(S)α(S) denote the maximum number of pairwise nonadjacent vertices in the subgraph G〈S〉G〈S〉 of GG induced by SS. If G〈S〉G〈S〉 is not complete, let κ(S)κ(S) denote the smallest number of vertices separating two vertices of SS and κ(S)=|S|-1κ(S)=|S|-1 otherwise. We prove that if α(S)⩽κ(S)α(S)⩽κ(S) and |S||S| is large enough (depending on α(S)α(S)), then GG is SS-pancyclable, that is contains cycles with exactly pp vertices of SS for every pp, 3⩽p⩽|S|3⩽p⩽|S|.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 11–12, 28 May 2007, Pages 1463–1466
نویسندگان
, , , ,