[seqfan] confusion over k-connected graphs
Brendan McKay
Brendan.McKay at anu.edu.au
Wed Jul 8 16:03:38 CEST 2015
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.
More information about the SeqFan
mailing list