首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 G be a graph of order n3. An even squared Hamiltonian cycle (ESHC) of G is a Hamiltonian cycle C=v1v2vnv1 of G with chords vivi+3 for all 1in (where vn+j=vj for j1). When n is even, an ESHC contains all bipartite 2-regular graphs of order n. We prove that there is a positive integer N such that for every graph G of even order nN, if the minimum degree is δ(G)n2+92, then G contains an ESHC. We show that the condition of n being even cannot be dropped and the constant 92 cannot be replaced by 1. Our results can be easily extended to even kth powered Hamiltonian cycles for all k2.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号