Pancyclicity when each cycle contains k chords

Abstract: For integers

n g e q k g e q 2

, let

c (n, k)

be the minimum number of chords that must be added to a cycle of length

n

so that the resulting graph has the property that for every

l i n k, k + 1, d o t s, n

, there is a cycle of length

l

that contains exactly

k

of the added chords. Affif Chaouche, Rutherford, and Whitty introduced the function

c (n, k)

. They showed that for every integer

k g e q 2

,

c (n, k) g e q O m e g a_{k} (n^{1 / k})

and they asked if

n^{1 / k}

gives the correct order of magnitude of

c (n, k)

for

k g e q 2

. Our main theorem answers this question as we prove that for every integer

k g e q 2

, and for sufficiently large

n

,

c (n, k) l e q k l c e i l n^{1 / k} c e i l + k^{2}

. This upper bound, together with the lower bound of Affif Chaouche et. al., shows that the order of magnitude of

c (n, k)

is

n^{1 / k}

.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Pancyclicity when each cycle contains \(k\) chords