On the Connectivity of Graphs Embedded in Surfaces
β Scribed by Michael D Plummer; Xiaoya Zha
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 376 KB
- Volume
- 72
- Category
- Article
- ISSN
- 0095-8956
No coin nor oath required. For personal study only.
β¦ Synopsis
In a 1973 paper, Cooke obtained an upper bound on the possible connectivity of a graph embedded in a surface (orientable or nonorientable) of fixed genus. Furthermore, he claimed that for each orientable genus #>0 (respectively, nonorientable genus #Γ >0, #Γ {2) there is a complete graph of orientable genus # (respectively, nonorientable genus #Γ ) and having connectivity attaining his bound. It is false that there is a complete graph of genus # (respectively, nonorientable genus #Γ ), for every # (respectively #Γ ) and that is the starting point of the present paper. Ringel and Youngs did show that for each #>0 (respectively, #Γ >0, #Γ {2) there is a complete graph K n which embeds in S # (respectively N #Γ ) such that n is the chromatic number of surface S # (respectively, the chromatic number of surface N #Γ ). One then easily observes that the connectivity of this K n attains the upper bound found by Cook. This leads us to define two kinds of connectivity bound for each orientable (or nonorientable) surface. We define the maximum connectivity } max of the orientable surface S # to be the maximum connectivity of any graph embeddable in the surface and the genus connectivity } gen (S # ) of the surface to be the maximum connectivity of any graph which genus embeds in the surface. For nonorientable surfaces, the bounds } max (N #Γ ) and } gen (N #Γ ) are defined similarly. In this paper we first study the uniqueness of graphs possessing connectivity } max (S # ) or } max (N #Γ ). The remainder of the paper is devoted to the study of the spectrum of values of genera in the intervals [#(K n )+1, #(K n+1 )] and [#Γ (K n )+1, #Γ (K n+1 )] with respect to their genus and maximum connectivities.
π SIMILAR VOLUMES
In this article, we show that there exists an integer k(Ξ£)
A well-known Tutte's theorem claims that every 3-connected planar graph has a convex embedding into the plane. Tutte's arguments also show that, moreover, for every nonseparating cycle C of a 3-connected graph G, there exists a convex embedding of G such that C is a boundary of the outer face in thi
## Abstract An __m__β__covering__ of a graph __G__ is a spanning subgraph of __G__ with maximum degree at most __m__. In this paper, we shall show that every 3βconnected graph on a surface with Euler genus __k__ββ₯β2 with sufficiently large representativity has a 2βconnected 7βcovering with at most