2013/12/01 by Sean T. Griffin, Griffin, Sean
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1312.0274
openalex publication_date 2013/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A pancyclic graph is a simple graph containing a cycle of length k for all 3≤ k≤ 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≤ 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.