Disjoint hamiltonian cycles in bipartite graphs

AbstractLet G=(X,Y) be a bipartite graph and define σ22(G)=min{d(x)+d(y):xy∉E(G),x∈X,y∈Y}. Moon and Moser [J. Moon, L. Moser, On Hamiltonian bipartite graphs, Israel J. Math. 1 (1963) 163–165. MR 28 # 4540] showed that if G is a bipartite graph on 2n vertices such that σ22(G)≥n+1, then G is hamiltonian, sharpening a classical result of Ore [O. Ore, A note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55] for bipartite graphs. Here we prove that if G is a bipartite graph on 2n vertices such that σ22(G)≥n+2k−1, then G contains k edge-disjoint hamiltonian cycles. This extends the result of Moon and Moser and a result of R. Faudree et al. [R. Faudree, C. Rousseau, R. Schelp, Edge-disjoint Hamiltonian cycles, Graph Theory Appl. Algorithms Comput. Sci. (1984) 231–249]