Minimal Pancyclicity

Abstract

A pancyclic graph is a simple graph containing a cycle of length $k$ for all $3\le k\le n$. Let $m(n)$ be the minimum number of edges of all pancyclic graphs on $n$ vertices. Exact values are given for $m(n)$ for $n\le 37$, combining calculations from an exhaustive search on graphs with up to 29 vertices with a construction that works for up to 37 vertices. The behavior of $m(n)$ in general is also explored, including a proof of the conjecture that $m(n+1)>m(n)$ for all $n$ in some special cases.

arXiv comment6 pages

Cited by in corpus (1)

• Pancyclicity when each cycle contains k chords