[math-fun] Extremal graph problem: avoid 5-cycles
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.
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.
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.
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
participants (2)
-
Allan Wechsler -
Michael Kleber