[seqfan] Re: Max no. of edges in graph with no 4-cycles

Brendan McKay Brendan.McKay at anu.edu.au
Tue Mar 8 09:20:56 CET 2022


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
>
>
>
> 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
>>
>>
> --
> 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



More information about the SeqFan mailing list