Maximum Number of Contractible Edges on Hamiltonian Cycles of a 3-Connected Graph |
| |
Authors: | Kyo Fujita |
| |
Affiliation: | (1) Department of Applied Mathematics, Science University of Tokyo, 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan. e-mail: kyo@ha.bekkoame.ne.jp, JP |
| |
Abstract: | We show that if G is a 3-connected hamiltonian graph of order at least 5, then there exists a hamiltonian cycle C of G such that the number of contractible edges of G which are on C is greater than or equal to . Received: July 31, 2000 Final version received: December 12, 2000 Acknowledgments. I would like to thank Professor Yoshimi Egawa for the help he gave to me during the preparation of this paper. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|