Yes, now that's what I expect: that the few cases for which A(n) > A002620(n) will turn out to be flukes. At the moment the only examples I know are A(3) = 3, A(4) = 6, A(5) = 7. On Fri, May 10, 2013 at 10:11 AM, Michael Kleber <michael.kleber@gmail.com>wrote:
Don't you expect K_{floor(n/2), ceiling(n/2)} to be best for large n? E.g. A(18) is at least 81, from K_9,9. Though certainly you've beaten that for small graphs.
--Michael
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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun