[seqfan] Re: confusion over k-connected graphs

Wed Jul 8 18:58:44 CEST 2015

PS
Brendan, I edited A052445 (partially) and A086216,
and I created a new entry A259862 using your data: this is a triangle
giving no of graphs with connectivity exactly k.  I also wrote
to Eric W. about the errors in A052445.

If you could create another table with the numbers of graphs
with connectivity k, meaning k or more, I would
create another entry for that.  Or (safer) you
could do it yourself, following the example of A259862.

In any case, thanks for pointing out these problems!

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 12:26 PM, Neil Sloane <njasloane at gmail.com> wrote:

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