pith. sign in

arxiv: 1212.3633 · v2 · pith:OET2LBCMnew · submitted 2012-12-14 · 🧮 math.CO · cs.DM

Pancyclicity when each cycle must pass exactly k Hamilton cycle chords

classification 🧮 math.CO cs.DM
keywords chordscycleeverymustaddedexactlylengthpancyclicity
0
0 comments X
read the original abstract

It is known that $\Theta(\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, $\Theta(n)$ chords are required. A possibly `intermediate' variation is the following: given $k$, $1\leq k\leq n$, how many chords must be added to ensure that there exist cycles of every length each of which passes exactly $k$ chords? For fixed $k$, we establish a lower bound of $\Omega\big(n^{1/k}\big)$ on the growth rate.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.