[seqfan] Re: Max no. of edges in graph with no 4-cycles
Brendan McKay
Brendan.McKay at anu.edu.au
Tue Mar 8 09:46:35 CET 2022
Hi Neil,
I added the bounds.
I have a large collection of extremal graphs of various types and I'm slowly
developing a web site to host them. I can give the C4-free extremal graphs
to anyone who asks.
Cheers, Brendan.
On 8/3/2022 7:34 pm, Neil Sloane wrote:
> Hi Brendan! Thanks for those additional terms.
> I think people would find it helpful to see the lower bounds for 40 to
> 49 - could you add them in the COMMENTS section?
>
> I see you also extended A335830, which gives the number of optimal graphs.
>
> Are the actual graphs available anywhere on your web site?
>
> Best regards
> Neil
>
> Neil J. A. Sloane, Chairman, OEIS Foundation.
> Also Visiting Scientist, Math. Dept., Rutgers University,
> Email: njasloane at gmail.com
>
>
>
> On Tue, Mar 8, 2022 at 3:21 AM Brendan McKay via SeqFan
> <seqfan at list.seqfan.eu> wrote:
>
> I added a(32)-a(39) to A006855, namely 92,96,102,106,110,113,117,122.
>
> I also have lower bounds for a(40)-a(49) that are probably exact, but
> I didn't prove them.
>
> Brendan.
>
> On 8/3/2022 4:36 am, Neil Sloane wrote:
> > PS Allan Wechsler kindly pointed me to A006855.
> >
> > Best regards
> > Neil
> >
> > Neil J. A. Sloane, Chairman, OEIS Foundation.
> > Also Visiting Scientist, Math. Dept., Rutgers University,
> > Email:njasloane at gmail.com <mailto:Email%3Anjasloane at gmail.com>
> >
> >
> >
> > On Mon, Mar 7, 2022 at 11:45 AM Neil Sloane<njasloane at gmail.com>
> wrote:
> >
> >> Let b(n) be the maximum number of edges in a graph on n nodes that
> >> contains no 4-cycle.
> >>
> >> It seems to start (for n>=1) 0, 1, 3, 4, 7, 9?
> >>
> >> Is it missing from the OEIS?
> >>
> >>
> >> This question came up because M S Smith seems to have proved
> that b(n) is
> >> an upper bound on Stan Wagon's Problem of the Week #1321 (and
> also on
> >> A347301). Happy to send anyone who is interested a copy of
> Smith's email.
> >>
> >>
> >> Best regards
> >> Neil
> >>
> >> Neil J. A. Sloane, Chairman, OEIS Foundation.
> >> Also Visiting Scientist, Math. Dept., Rutgers University,
> >> Email:njasloane at gmail.com <mailto:Email%3Anjasloane at gmail.com>
> >>
> >>
> > --
> > Seqfan Mailing list
> -https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cde99c82a440040d89a4308da00610b93%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637823232438822531%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=hWxfowHwIQzV5kBLPPPTj7t3J5qbkS2B8zLw8pjVdf4%3D&reserved=0
> <https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7CBrendan.McKay%40anu.edu.au%7C00aac56ebd344eb7773508da00de740a%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637823252669835992%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=SuuBYIpHVY0Es5zknjrmlSLT6iJeM0lUzCfrXaQV0ik%3D&reserved=0>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
> <https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7CBrendan.McKay%40anu.edu.au%7C00aac56ebd344eb7773508da00de740a%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637823252669835992%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=SuuBYIpHVY0Es5zknjrmlSLT6iJeM0lUzCfrXaQV0ik%3D&reserved=0>
>
More information about the SeqFan
mailing list