[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