2022/10/27 by Lucas Blakeslee, Blakeslee, Lucas
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2210.15162
The genus of a graph is a topological invariant that measures the minimum genus of a surface on which the graph can be embedded without any edges crossing. Graph genus plays a fundamental role in topological graph theory, used to classify and study different types of graphs and their properties. We show that, for any integer d ≥ 2, the genus of a random d-regular graph on n nodes is ((d - 2))/(4)n(1 - ε) with high probability for any ε > 0.