Article ID Journal Published Year Pages File Type
418594 Discrete Applied Mathematics 2015 19 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,