OFFSET
1,6
COMMENTS
A graph is weakly pancyclic if it contains cycles of all lengths between its girth and its circumference. Acyclic graphs are considered to be weakly pancyclic.
All graphs on at most 5 nodes are weakly pancyclic, so a(n) = 0 when n <= 5.
Brandt (1997) conjectures that a(n) = floor((n-1)*(n-3)/4) + 5 for n >= 6. The conjecture is false for n = 8, since there exists a (unique) non-bipartite, not weakly pancyclic graph (shown below) with 8 nodes and 13 edges, showing that a(8) >= 14. This graph contains cycles of lengths 3, 4, 5, 6, and 8, but none of length 7.
O
/|\
/ O \
/ | \
/ O \
/ / \ \
/ / \ \
// \\
O ----------- O
\\ //
\ \ / /
\ \ / /
\ O /
\ | /
\ O /
\|/
O
LINKS
Béla Bollobás and Andrew Thomason, Weakly pancyclic graphs, Journal of Combinatorial Theory Series B 77 (1999), 121-137.
Stephan Brandt, A sufficient condition for all short cycles, Discrete Applied Mathematics 79 (1997), 63-66.
FORMULA
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Pontus von Brömssen, May 29 2023
STATUS
approved