cp's OEIS Frontend

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

%I A363364 #7 Jun 02 2023 08:39:31
%S A363364 0,0,0,0,0,8,11,14,17,20
%N A363364 Least nonnegative integer k such that all non-bipartite graphs with n nodes and at least k edges are weakly pancyclic.
%C A363364 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.
%C A363364 All graphs on at most 5 nodes are weakly pancyclic, so a(n) = 0 when n <= 5.
%C A363364 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.
%C A363364          O
%C A363364         /|\
%C A363364        / O \
%C A363364       /  |  \
%C A363364      /   O   \
%C A363364     /  /   \  \
%C A363364    / /       \ \
%C A363364   //           \\
%C A363364   O ----------- O
%C A363364   \\           //
%C A363364    \ \       / /
%C A363364     \  \   /  /
%C A363364      \   O   /
%C A363364       \  |  /
%C A363364        \ O /
%C A363364         \|/
%C A363364          O
%H A363364 Béla Bollobás and Andrew Thomason, <a href="https://doi.org/10.1006/jctb.1999.1916">Weakly pancyclic graphs</a>, Journal of Combinatorial Theory Series B 77 (1999), 121-137.
%H A363364 Stephan Brandt, <a href="https://doi.org/10.1016/S0166-218X(97)00032-2">A sufficient condition for all short cycles</a>, Discrete Applied Mathematics 79 (1997), 63-66.
%F A363364 a(n) >= floor((n-1)*(n-3)/4) + 5 = A028309(n-1) + 2 for n >= 6 (Brandt, 1997).
%F A363364 a(n) <= floor((n-1)^2/4) + 2 = A290743(n-1) (Brandt, 1997).
%F A363364 a(n) <= floor(n^2/4) - n + 59 (Bollobás and Thomason, 1999).
%Y A363364 Cf. A028309, A290743, A363362, A363363.
%K A363364 nonn,more
%O A363364 1,6
%A A363364 _Pontus von Brömssen_, May 29 2023