کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418594 681693 2015 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Weakly bipancyclic bipartite graphs
ترجمه فارسی عنوان
گرافیک دو طرفه ضخیم دو طرفه
کلمات کلیدی
گراف دو طرفه، چرخه همیلتون تقریبا دوقطبی حداقل درجه
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We investigate the set of cycle lengths occurring in bipartite graphs with large minimum degree. A bipartite graph is weakly bipancyclic   if it contains cycles of every even length between the length of a shortest and a longest cycle. In this paper, it is shown that if G=(V1,V2,E)G=(V1,V2,E) is a bipartite graph with minimum degree at least n/3+4n/3+4, where n=max{|V1|,|V2|}, then GG is a weakly bipancyclic graph of girth 4. This improves a theorem of Tian and Zang (1989), which asserts that if GG is a Hamilton bipartite graph on 2n2n(n≥60)(n≥60) vertices with minimum degree greater than 2n/5+22n/5+2, then GG is bipancyclic (i.e.,  GG contains cycles of every even length between 4 and 2n2n). By combining the main result of our paper with a theorem of Jackson and Li (1994), we obtain that every 2-connected kk-regular bipartite graph on at most 6k−386k−38 vertices is bipancyclic.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 194, 30 October 2015, Pages 102–120
نویسندگان
, ,