کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418594 | 681693 | 2015 | 19 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Applied Mathematics - Volume 194, 30 October 2015, Pages 102–120