𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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


3-Coloring graphs embedded in surfaces
✍ Zhao, Yue πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 66 KB πŸ‘ 3 views

In this article, we show that there exists an integer k(Ξ£)

On convex embeddings of planar 3-connect
✍ Kelmans, Alexander πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 167 KB πŸ‘ 2 views

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

2-connected 7-coverings of 3-connected g
✍ Ken-ichi Kawarabayashi; Atsuhiro Nakamoto; Katsuhiro Ota πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 116 KB πŸ‘ 1 views

## 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