Two edge-disjoint hamiltonian cycles in graphs |
| |
Authors: | Mingchu Li |
| |
Institution: | 1. Department of Mathematics and Mechanics, University of Science and Technology Beijing, 30 College Road, 100083, Beijing, P. R. China
|
| |
Abstract: | E. Schmeichel and D. Hayes showed that ifG is a 2-connected graph withd(u) +d(v)≥n ?1 for every pair of nonadjacent vertices andv, then G has a Hamiltonian cycle unlessG is the graph of Fig. 2 (b). In this paper, it is proved that, under almost the same conditions as Schmeichel and Hayes’s Theorem, namely,G is a 2-connected graph of ordern (n ≥ 40) with δ(G) ≥ 7 for every pair of nonadjacent vertices andv, G has two edge-disjoint Hamiltonian cycles unlessG is one of the graphs in Fig. 1 or Fig. 2, and this conclusion is best possible. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|