Abstract
It is known that Θ(log n) chords must be added to an n-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, Θ(n) chords are required. A possibly ‘intermediate’ variation is the following: given k, 1 ≤ k ≤ n, how many chords must be added to ensure that there exist cycles of every possible length each of which
passes exactly k chords? For fixed k, we establish a lower bound of Ω n 1/k� on the growth rate.
Original language | English |
---|---|
Pages (from-to) | 533-539 |
Journal | Discussiones Mathematicae Graph Theory |
DOIs | |
Publication status | Published - 30 Sept 2015 |