Cubic graphs and related triangulations on orientable surfaces

MaRDI QIDQ1700799zbMATH OpenFDO

Authors W. Fang, Mihyun Kang, M. Moßhammer, Philipp Sprüssel

Publication date 22 February 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.01440, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p30

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

analytic combinatoricsasymptotic enumerationcubic graphsgraphs on surfacestriangulations

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30)

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}gamm{a}^{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$, $gge1$, has exactly one non-planar component.

Review text

Summary: Let \(\mathbb{S}_g\) be the orientable surface of genus \(g\) for a fixed non-negative integer \(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/2(g-1)-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, for \(g\geq 1\), we prove that a typical cubic multigraph embeddable on \(\mathbb{S}_g\) has exactly one non-planar component.

Recommendations

• Enumeration of cubic multigraphs on orientable surfaces
• On cubic graphs which are irreducible for nonorientable surfaces
• Triangulations of orientable surfaces by complete tripartite graphs
• Cubic planar graphs and Legendrian surface theory
• On Polyhedral Embeddings of Cubic Graphs
• Publication:4864467
• On the cubicity of certain graphs
• Orientation spectra of cubic graphs
• Cubical graphs and cubical dimensions
• The construction of cubic maps on orientable surfaces

Cites work

• A Census of Planar Maps
• A Census of Planar Triangulations
• A pattern for the asymptotic number of rooted maps on surfaces
• Almost all rooted maps have large representativity
• Analytic combinatorics
• Asymptotic enumeration and limit laws for graphs of fixed genus
• Asymptotic enumeration and limit laws of planar graphs
• Asymptotic enumeration of labelled graphs by genus
• Enumeration of rooted cubic planar maps
• Enumeration of Triangulations of the Disk
• Generating unlabeled connected cubic planar graphs uniformly at random
• Graphs on surfaces
• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 16301 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• On random planar graphs, the number of planar graphs and their triangulations
• On the eigenvalues in problems with spherical symmetry
• On the probability of planarity of a random graph near the critical point
• Random cubic planar graphs
• Random cubic planar graphs revisited
• Random planar graphs
• Singularity Analysis of Generating Functions
• The asymptotic number of rooted 2-connected triangular maps on a surface
• The asymptotic number of rooted maps on a surface
• The asymptotic number of rooted maps on a surface. II: Enumeration by vertices and faces
• The asymptotic number of rooted nonseparable maps on a surface
• The birth of the giant component
• The number of labeled 2-connected planar graphs
• The number of rooted 2-connected triangular maps on the projective plane
• The number of rooted triangular maps on a surface
• Two critical periods in the evolution of random planar graphs

Cited in

(13)

• On some graphs related to regular, oriented triangular maps
• A character approach to directed genus distribution of graphs: the bipartite single-black-vertex case
• Orientation spectra of cubic graphs
• Cube-contractions in 3-connected quadrangulations
• Enumeration of cubic multigraphs on orientable surfaces
• Graph relations, clique divergence and surface triangulations
• Phase transitions in graphs on orientable surfaces
• Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
• First-passage percolation on random simple triangulations
• Random cubic planar graphs converge to the Brownian sphere
• The genus distribution of cubic graphs and asymptotic number of rooted cubic maps with high genus
• The uniform infinite cubic planar graph
• The scaling limit of random cubic planar graphs

This page was built for publication: Cubic graphs and related triangulations on orientable surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1700799)