کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647907 1342382 2012 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hamiltonian cycles with all small even chords
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Hamiltonian cycles with all small even chords
چکیده انگلیسی

Let GG be a graph of order n≥3n≥3. An even squared Hamiltonian cycle   (ESHC) of GG is a Hamiltonian cycle C=v1v2…vnv1C=v1v2…vnv1 of GG with chords vivi+3vivi+3 for all 1≤i≤n1≤i≤n (where vn+j=vjvn+j=vj for j≥1j≥1). When nn is even, an ESHC contains all bipartite 22-regular graphs of order nn. We prove that there is a positive integer NN such that for every graph GG of even   order n≥Nn≥N, if the minimum degree is δ(G)≥n2+92, then GG contains an ESHC. We show that the condition of nn being even cannot be dropped and the constant 9292 cannot be replaced by 11. Our results can be easily extended to even  kkth powered Hamiltonian cycles   for all k≥2k≥2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 6, 28 March 2012, Pages 1226–1240
نویسندگان
, , , ,