학술논문
Low independence number and Hamiltonicity implies pancyclicity.
Document Type
Article
Author
Source
Subject
*HAMILTONIAN graph theory
*GRAPH theory
*
Language
ISSN
0364-9024
Abstract
A graph on n vertices is called pancyclic if it contains a cycle of every length 3≤ℓ≤n. Given a Hamiltonian graph G with independence number at most k, we are looking for the minimum number of vertices f(k) that guarantees that G is pancyclic. The problem of finding f(k) was raised by Erdős in 1972, who showed that f(k)≤4k4 and conjectured that f(k)=Θ(k2). Improving on a result of Lee and Sudakov, we show that f(k)=O(k11/5). [ABSTRACT FROM AUTHOR]