Hamiltonicity, independence number, and pancyclicity |
| |
Authors: | Choongbum Lee Benny Sudakov |
| |
Institution: | Department of Mathematics, UCLA, Los Angeles, CA, 90095, United States |
| |
Abstract: | A graph on n vertices is called pancyclic if it contains a cycle of length ? for all 3≤?≤n. In 1972, Erd?s proved that if G is a Hamiltonian graph on n>4k4 vertices with independence number k, then G is pancyclic. He then suggested that n=Ω(k2) should already be enough to guarantee pancyclicity. Improving on his and some other later results, we prove that there exists a constant c such that n>ck7/3 suffices. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|