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 is called a -cycle. A non-induced cycle is called a chorded cycle. Let be an integer with . Then a graph of order is chorded pancyclic if contains a chorded -cycle for every integer with . Cream, Gould and Hirohata (Australas. J. Combin. 67 (2017), 463–469) proved that a graph of order satisfying for every pair of nonadjacent vertices , in is chorded pancyclic unless is either or , the Cartesian product of and . They also conjectured that if is Hamiltonian, we can replace the degree sum condition with the weaker density condition
and still guarantee the same conclusion. In this paper, we prove this conjecture by showing that if a graph of order with contains a -cycle, then contains a chorded -cycle, unless and is either or , Then observing that and are exceptions only for , we further relax the density condition for sufficiently large . |
| |
Keywords: | Pancyclic Weakly pancyclic Chorded pancyclic Chorded cycle |
本文献已被 ScienceDirect 等数据库收录! |
|