Cubic graphs and related triangulations on orientable surfaces

Abstract

Let ${\mathbb{S}}_g$ be the orientable surface of genus $g$. We show that the number of vertex-labelled cubic multigraphs embeddable on ${\mathbb{S}}_g$ with $2n$ vertices is asymptotically $c_g{n}^{5(g-1)/2-1}{\gamma }^{2n}(2n)!$, where $\gamma$ is an algebraic constant and $c_g$ is a constant depending only on the genus $g$. We also derive an analogous result for simple cubic graphs and weighted cubic multigraphs. Additionally we prove that a typical cubic multigraph embeddable on ${\mathbb{S}}_g$, $g\ge 1$, has exactly one non-planar component.

50 pages. An extended abstract of this paper has been published in the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb15), Electronic Notes in Discrete Mathematics (2015), 603--610