The genus of a random graph
type: Item
instance of: scholarly article
title: The genus of a random graph
zbMATH Open document ID: 0834.05023
DOI: 10.1016/0012-365X(95)00215-I
author: David A. Grable
author: Dan S. Archdeacon
published in: Discrete Mathematics
publication date: 1996-04-08T00:00:00Z
review text: The minimum number of handles (crosscaps) needed to embed a graph on an orientable (nonorientable) surface is shown to be close to \(pn^2/12\) \((pn^2/6)\) for almost every random graph of order \(n\) with edge probability \(p\).
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 790747
zbMATH Keywords: genus
zbMATH Keywords: embeddings
zbMATH Keywords: triangulations
zbMATH Keywords: surface
zbMATH Keywords: random graph
MaRDI profile type: Publication
cites work: Q3950589
cites work: Q3682518
cites work: Q3286850
cites work: Near perfect coverings in graphs and hypergraphs
cites work: Q3757929
cites work: Asymptotic behavior of the chromatic index for hypergraphs
cites work: Q4773723
cites work: The graph genus problem is NP-complete
cites work: Triangulating a surface with a prescribed graph
full work available at URL: 0012-365x(95)00215-i
OpenAlex ID: W2078504643
Wikidata QID: Q127109821
Recommended article: On the genus of a random graph
Recommended article: The Genus of a Random Bipartite Graph
Recommended article: On the average genus of the random graph
Recommended article: The genus of the Erdős‐Rényi random graph and the fragile genus property
Recommended article: The genus of the Erd\H{o}s-R\'enyi random graph and the fragile genus property
Recommended article: Random generations of the countable random graph
Recommended article: Q3414282
Recommended article: Genus distributions for two classes of graphs
Recommended article: Q3013519
description: scientific article; zbMATH DE number 790747