کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649317 | 1342450 | 2009 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Disjoint hamiltonian cycles in bipartite graphs Disjoint hamiltonian cycles in bipartite graphs](/preview/png/4649317.png)
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].
Journal: Discrete Mathematics - Volume 309, Issue 12, 28 June 2009, Pages 3811–3820