Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: On the connectivity of graphs embedded in surfaces II | On the connectivity of graphs embedded in surfaces II Michael D. Plummer Department of Mathematics Vanderbilt University Nashville TN 37240 UsA Xiaoya Zha Department of Mathematical Sciences Middle Tennessee State University Murfreesboro TN 37132 USA xzha@ Submitted February 6 2002 Accepted September 12 2002 MR Subject Classification 05C10 05C40 Abstract Let Umax X denote the maximum value for the connectivity of any graph which embeds in the topological surface X. The connectivity interval for X is the set of integers in the interval 1 nmax X . Given an integer i in 1 nmax X it is a trivial problem to demonstrate that there is a graph Gi with connectivity i which also embeds in X. We will say that one can saturate the connectivity interval in this case. Note that no restrictions have been placed on the embeddings in the above problem however. What if we demand that the embeddings in question be 2-cell or even that they be genus embeddings The problem of saturating the connectivity interval for 2-cell embeddings will be solved completely in the present work. In connection with the apparently much harder saturation question for genus embeddings it will be shown that one can always saturate the subinterval 1 X _ . work supported by NSF Grant DMS-9622780 and Middle Tennessee State University Faculty Research Grant 1999 THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2002 R38 1 1. Introduction In his 1973 paper Cook C1 studied the relation between the connectivity of a graph and the surfaces into which it can be embedded. He proved that the following result holds for all surfaces except the plane G 5 Ự49 - 24x 2 where k G denotes the vertex connectivity of graph G and X is the Euler characteristic of any surface in which G embeds. Moreover Cook showed that these bounds are attained by complete graphs in all cases except the Klein bottle. In PZ1 we explored in more detail relations between the connectivity of embedded graphs .
