Weakly bipancyclic bipartite graphs

作者：Hu, Zhiquan^*; Sun, Jing

来源：Discrete Applied Mathematics, 2015, 194: 102-120.

DOI：10.1016/j.dam.2015.05.006

• Bipartite graph
• Hamiltonian cycle
• Weakly bipancyclic
• Minimum degree

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 = (V-1, V-2, E) is a bipartite graph with minimum degree at least n/3 + 4, where n = max {[V-1], [V-2]}, then G is a weakly bipancyclic graph of girth 4. This improves a theorem of Tian and Zang (1989), which asserts that if G is a Hamilton bipartite graph on 2n(n >= 60) vertices with minimum degree greater than 2n/5 + 2, then G is bipancyclic (i.e., G contains cycles of every even length between 4 and 2n). By combining the main result of our paper with a theorem of Jackson and Li (1994), we obtain that every 2-connected k-regular bipartite graph on at most 6k - 38 vertices is bipancyclic.

• 出版日期2015-10-30
• 单位湖北第二师范学院; 华中师范大学