On the connectivity of graphs embedded in surfaces. II

Michael D. Plummer ; Xiaoya Zha

The electronic journal of combinatorics, Tome 9 (2002)

Résumé

Let $\kappa_{max}(\Sigma)$ denote the maximum value for the connectivity of any graph which embeds in the topological surface $\Sigma$. The connectivity interval for $\Sigma$ is the set of integers in the interval $[1,\kappa_{max}(\Sigma)]$. Given an integer $i$ in $[1,\kappa_{max}(\Sigma)]$ it is a trivial problem to demonstrate that there is a graph $G_i$ with connectivity $i$ which also embeds in $\Sigma$. 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,\lfloor 0.7\kappa_{max}(\Sigma)\rfloor]$.

Détail

DOI : 10.37236/1654

Classification : 05C10, 05C40