Hamiltonian cycles with all small even chords |
| |
Authors: | Guantao Chen Katsuhiro Ota Akira Saito Yi Zhao |
| |
Institution: | 1. Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303, United States;2. Department of Mathematics, Keio University, 3-14-1 Hiyoshi, Kohoku-Ku, Yokohama 223-8522, Japan;3. Department of Computer Science, Nihon University, Sakurajosui 3-25-40, Setagaya-Ku, Tokyo 156-8550, Japan |
| |
Abstract: | Let be a graph of order . An even squared Hamiltonian cycle (ESHC) of is a Hamiltonian cycle of with chords for all (where for ). When is even, an ESHC contains all bipartite -regular graphs of order . We prove that there is a positive integer such that for every graph of even order , if the minimum degree is , then contains an ESHC. We show that the condition of being even cannot be dropped and the constant cannot be replaced by . Our results can be easily extended to even th powered Hamiltonian cycles for all . |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|