Edge disjoint cycles in graphs |
| |
Authors: | Li Hao |
| |
Abstract: | Ore proved in 1960 that if G is a graph of order n and the sum of the degrees of any pair of nonadjacent vertices is at least n, then G has a hamiltonian cycle. In 1986, Li Hao and Zhu Yongjin showed that if n ? 20 and the minimum degree δ is at least 5, then the graph G above contains at least two edge disjoint hamiltonian cycles. The result of this paper is that if n ? 2δ2, then for any 3 ? l1 ? l2 ? ? ? lk ? n, 1 = k = [(δ - 1)/2], such graph has K edge disjoint cycles with lengths l1, l2…lk, respectively. In particular, when l1 = l2 = ? = lk = n and k = [(δ - 1)/2], the graph contains [(δ - 1)/2] edge disjoint hamiltonian cycles. |
| |
Keywords: | |
|
|