Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649317 | Discrete Mathematics | 2009 | 10 Pages |
Let G=(X,Y)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 GG is a bipartite graph on 2n2n vertices such that σ22(G)≥n+1, then GG 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 GG is a bipartite graph on 2n2n vertices such that σ22(G)≥n+2k−1, then GG contains kk 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].