Disjoint hamiltonian cycles in bipartite graphs |
| |
Authors: | Michael Ferrara Thor Whalen |
| |
Institution: | a The University of Akron, Akron, OH 44325, United States b Emory University, Atlanta, GA 30322, United States c Atlanta, GA, United States d SABA Solutions, Paris, France |
| |
Abstract: | Let G=(X,Y) be a bipartite graph and define . 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 , 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 , 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]. |
| |
Keywords: | Graph Degree sum Bipartite Disjoint hamiltonian cycles |
本文献已被 ScienceDirect 等数据库收录! |
|