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


Cycles with a chord in dense graphs
Authors:Guantao Chen  Ronald J Gould  Xiaofeng Gu  Akira Saito
Institution:1. Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303, United States;2. Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, United States;3. Department of Mathematics, University of West Georgia, Carrollton, GA 30118, United States;4. Department of Information Science, Nihon University, Sakurajosui 3-25-40, Setagaya-Ku, Tokyo 156-8550, Japan
Abstract:A cycle of order k is called a k-cycle. A non-induced cycle is called a chorded cycle. Let n be an integer with n4. Then a graph G of order n is chorded pancyclic if G contains a chorded k-cycle for every integer k with 4kn. Cream, Gould and Hirohata (Australas. J. Combin. 67 (2017), 463–469) proved that a graph of order n satisfying degGu+degGvn for every pair of nonadjacent vertices u,  v in G is chorded pancyclic unless G is either Kn2,n2 or K3K2, the Cartesian product of K3 and K2. They also conjectured that if G is Hamiltonian, we can replace the degree sum condition with the weaker density condition |E(G)|14n2 and still guarantee the same conclusion. In this paper, we prove this conjecture by showing that if a graph G of order n with |E(G)|14n2 contains a k-cycle, then G contains a chorded k-cycle, unless k=4 and G is either Kn2,n2 or K3K2, Then observing that Kn2,n2 and K3K2 are exceptions only for k=4, we further relax the density condition for sufficiently large k.
Keywords:Pancyclic  Weakly pancyclic  Chorded pancyclic  Chorded cycle
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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