I just realized that this sequence is always at least as big is A002620, the "quarter-squares", which can be proved to correspond to the densest graphs lacking all odd cycles. (It turns out that you only have to forbid 3-cycles to force all the extreme examples to be bipartite.) So this sequence is not in OEIS, but it may be the same as A002620 after only a few differences. Can anyone find, for instance, a 20-vertex graph lacking 5-cycles that has more edges than K(10,10)? On Fri, May 10, 2013 at 9:46 AM, Allan Wechsler <acwacw@gmail.com> wrote:
While I wait for my approval from Seqfans (why did it take me so long to subscribe? I think it's because I was getting OEIS editor mail, and wrongly assumed it was the same thing) here's a sequence for which I would love to know the next couple of entries.
What is the largest number of edges possessed by a graph that lacks 5-cycles? These graphs are, as usual, forbidden from having self-loops or multiple edges.
A(1 .. 4) = 0, 1, 3, 6. I am pretty sure that A(5) = 7; in other words, you can't do better than K4 plus a whisker. If A(6) is anything bigger than 9 I will be extremely surprised. There are only seven sequences in OEIS matching 0, 1, 3, 6, 7, 9. I know that A(7) >= 12, and only three of the seven sequences satisfy that constraint.
All the sequences except A047242 (0, 1, or 3 mod 6) are eliminated by the fact that A(1+3n) >= 6n; this number of vertices is achieved by n copies of K4 sharing one vertex.
And finally, A(18) >= 36, which rules out A047242. My example here is a necklace of 6 copies of K4, arranged in a 6-cycle, each sharing one vertex with the next.
So I am reasonably sure this sequence is missing from OEIS, but would like some confirmation from other funsters.