ON THE CONNECTIVITY OF GRAPHS EMBEDDED IN SURFACES

In a 1973 paper. Cooke obtained an upper bound on the possible connect ivity of a graph embedded in a surface (orientable or nonorientable) o f fixed genus. Furthermore, he claimed that for each orientable genus y>0 (respectively, nonorientable genus (y) over bar>0, (y) over bar no t equal 2) there is a complete graph of orientable genus y (respective ly, nonorientable genus (y) over bar) and having connectivity attainin g his bound. It is false that there is a complete graph of genus y (re spectively, nonorientable genus (y) over bar), for every y (respective ly (y) over bar) and that is the starting point of the present paper. Ringer and Youngs did show that for each y>0 (respectively, (y) over b ar>0, (y) over bar not equal 2) there is a complete graph K-n which em beds in S-y (respectively N-(y over bar)) such that n is the chromatic number of surface S-y (respectively, the chromatic number of surface N-(y over bar)). One then easily observes that the connectivity of thi s K-n attains the upper bound found by Cook. This leads us to define t wo kinds of connectivity bound for each orientable (or nonorientable) surface. We define the maximum connectivity K-max of the orientable su rface S-y to be the maximum connectivity of any graph embeddable in th e surface and the genus connectivity K-gen (S-y) of the surface to be the maximum connectivity of any graph which genus embeds in the surfac e. For nonorientable surfaces, the bounds K-max(N-(y over bar)) and K- gen(N-(y over bar)) are defined similarly. In this paper we first stud y the uniqueness of graphs possessing connectivity K-max(S-y) or K-max (N-(y over bar)). The remainder of the paper is devoted to the study o f the spectrum of values of genera in the intervals [y(K-n) + 1,y(Kn+1 )] and [(y) over bar(K-n) + 1,(y) over bar(Kn+1)] with respect to thei r genus and maximum connectivities. (C) 1998 Academic Press.