[seqfan] Re: confusion over k-connected graphs

[Neil Sloane]

Brendan, Thanks for those comments!

I will forward your message to Eric Weisstein, who created those two
entries.
In the mean time I will make some repairs to the entries.


Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com


On Wed, Jul 8, 2015 at 10:03 AM, Brendan McKay <Brendan.McKay at anu.edu.au>
wrote:

> I had cause to think about the number of 4-connected graphs and found
> trouble on OEIS.
>
> Specifically, there are two sequences:
>
> A052445        Number of simple 4-connected unlabeled n-node graphs.
> a(1)=0, a(2)=0, a(3)=0, a(4)=1, a(5)=0, a(6)=3, a(7)=21
>
> A086216        Number of 4-connected graphs on n nodes.
> a(5)=1, a(6)=4, a(7)=25, a(8)=384, a(9)=14480, a(10)=1211735
>
> Except for the "unlabeled", which actually applies to both, the
> descriptions are the same.  Both refer to Weisstein at
> http://mathworld.wolfram.com/k-ConnectedGraph.html .  But they disagree.
>
> Examination of the numbers suggests that A052445 is intended to be "Number
> of simple unlabeled n-node graphs with connectivity exactly 4", while
> A086216 is correctly described (4-connected means connectivity greater than
> or equal to 4).
>
> However, A052445 has an error in that it should have a(4)=0, a(5)=1.  I am
> not aware of any current graph theorist working on connectivity issues who
> considers the complete graph on n nodes as having connectivity other than
> n-1 (except perhaps for K_1, which doesn't matter).  The trauma (starting
> with thousands of wrong theorems) of having a graph with connectivity
> greater than its minimum degree effectively excludes the value n.  A086216
> does this correctly.
>
> Looking at the Weisstein page, we read (preposterously) "Note that there
> is a unique n-connected n-node graph, namely, the complete graph K_n."
> However, the table of values given does not agree with that, nor does it
> agree with the correct definition.  To make it match Weisstein's
> definition, insert a "0" after each leading "1" in the table.  To make it
> match the correct definition, add an extra leading  "0" to each row.
>
> I doubt that connectivity 4 is the only connectivity with this problem.  I
> hope someone with more time than me can sort this out. To assist, here are
> counts by connectivity.
>
> n=2
>
>> C        1 graphs with connectivity 0
>> C        1 graphs with connectivity 1
>>
>
> n=3
>
>> C        2 graphs with connectivity 0
>> C        1 graphs with connectivity 1
>> C        1 graphs with connectivity 2
>>
>
> n=4
>
>> C        5 graphs with connectivity 0
>> C        3 graphs with connectivity 1
>> C        2 graphs with connectivity 2
>> C        1 graphs with connectivity 3
>>
>
> n=5
>
>> C       13 graphs with connectivity 0
>> C       11 graphs with connectivity 1
>> C        7 graphs with connectivity 2
>> C        2 graphs with connectivity 3
>> C        1 graphs with connectivity 4
>>
>
> n=6
>
>> C       44 graphs with connectivity 0
>> C       56 graphs with connectivity 1
>> C       39 graphs with connectivity 2
>> C       13 graphs with connectivity 3
>> C        3 graphs with connectivity 4
>> C        1 graphs with connectivity 5
>>
>
> n=7
>
>> C      191 graphs with connectivity 0
>> C      385 graphs with connectivity 1
>> C      332 graphs with connectivity 2
>> C      111 graphs with connectivity 3
>> C       21 graphs with connectivity 4
>> C        3 graphs with connectivity 5
>> C        1 graphs with connectivity 6
>>
>
> n=8
>
>> C     1229 graphs with connectivity 0
>> C     3994 graphs with connectivity 1
>> C     4735 graphs with connectivity 2
>> C     2004 graphs with connectivity 3
>> C      345 graphs with connectivity 4
>> C       34 graphs with connectivity 5
>> C        4 graphs with connectivity 6
>> C        1 graphs with connectivity 7
>>
>
> n=9
>
>> C    13588 graphs with connectivity 0
>> C    67014 graphs with connectivity 1
>> C   113176 graphs with connectivity 2
>> C    66410 graphs with connectivity 3
>> C    13429 graphs with connectivity 4
>> C      992 graphs with connectivity 5
>> C       54 graphs with connectivity 6
>> C        4 graphs with connectivity 7
>> C        1 graphs with connectivity 8
>>
>
> n=10
>
>> C   288597 graphs with connectivity 0
>> C  1973029 graphs with connectivity 1
>> C  4629463 graphs with connectivity 2
>> C  3902344 graphs with connectivity 3
>> C  1109105 graphs with connectivity 4
>> C    99419 graphs with connectivity 5
>> C     3124 graphs with connectivity 6
>> C       81 graphs with connectivity 7
>> C        5 graphs with connectivity 8
>> C        1 graphs with connectivity 9
>>
>
> n=11
>
>> C  12297299 graphs with connectivity 0
>> C 105731474 graphs with connectivity 1
>> C 327695586 graphs with connectivity 2
>> C 388624106 graphs with connectivity 3
>> C 162318088 graphs with connectivity 4
>> C  21500415 graphs with connectivity 5
>> C    820956 graphs with connectivity 6
>> C      9813 graphs with connectivity 7
>> C       121 graphs with connectivity 8
>> C         5 graphs with connectivity 9
>> C         1 graphs with connectivity 10
>>
>
> Cheers, Brendan.
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>