A363364 Least nonnegative integer k such that all non-bipartite graphs with n nodes and at least k edges are weakly pancyclic.

0, 0, 0, 0, 0, 8, 11, 14, 17, 20

Offset: 1

Author

Pontus von Brömssen, May 29 2023

Keywords

• nonn
• more

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.

Crossrefs

Cf. A028309, A290743, A363362, A363363.

Formula

a(n) >= floor((n-1)*(n-3)/4) + 5 = A028309(n-1) + 2 for n >= 6 (Brandt, 1997).

a(n) <= floor((n-1)^2/4) + 2 = A290743(n-1) (Brandt, 1997).

a(n) <= floor(n^2/4) - n + 59 (Bollobás and Thomason, 1999).