Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418594 | Discrete Applied Mathematics | 2015 | 19 Pages |
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.