[seqfan] graphs by connectivity

Brendan McKay bdm at cs.anu.edu.au
Sun Apr 18 13:28:30 CEST 2010


I am concerned about these:

%S A052442 1,0,1,3,11,56,385
%N A052442 Number of simple 1-connected unlabeled n-node graphs.
%O A052442 1,4

%S A052443 0,1,0,2,7,39,332
%N A052443 Number of simple 2-connected unlabeled n-node graphs.
%O A052443 1,4

%S A052444 0,0,1,0,2,13,111
%N A052444 Number of simple 3-connected unlabeled n-node graphs.
%O A052444 1,5

%S A052445 0,0,0,1,0,3,21
%N A052445 Number of simple 4-connected unlabeled n-node graphs.
%O A052445 1,6

There are two problems. The first problem is that the names are
wrong. These counts are of graphs with a given exact connectivity.
For example "3-connected" means "connectivity at least 3", but (for
example), 111 is the number of 7-vertex graphs with connectivity
exactly 3.  The sequences for "k-connected" are A001349, A002218,
A006290, A086216, A086217.

The second problem is that the complete graph K(n) is listed as
having connectivity n. Complete graphs have no cut-sets at all, so
the usually definition can't be applied, but I'm sure that with the
possible exception of K(1), the connectivity of K(n) is almost always
be taken to be n-1.  Otherwise anomalies occur (such as connectivity
greater than minimum degree).

I have counted all the graphs up to 12 vertices by connectivity and
will correct and update these sequences (and also update A086216/7).
but I thought I'd post here first in case someone disagrees.

Brendan.





More information about the SeqFan mailing list