Structure for a graph with average genus (Q2504073)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Structure for a graph with average genus |
scientific article |
Statements
Structure for a graph with average genus (English)
0 references
22 September 2006
0 references
The average genus of a connected graph \(G\) is the expected value of the genus random variable, over all labeled 2-cell imbeddings of \(G\) into closed orientable 2-manifolds, using the uniform distribution. \textit{J. Chen}, \textit{J. L. Gross} and \textit{R. G. Rieper} [J. Graph Theory 19, 281--296 (1995; Zbl 0819.05022)] showed that the average genus for a graph of maximum degree at most 3 is at least \(1/2\) its maximum genus. The present authors describe the structure of those graphs having maximum degree at most 3 which attain the lower bound above. They also show that if \(G\) and \(H\) have the same average genus and \(H\) is a subgraph of \(G\), then \(G\) can be obtained from \(H\) by a series of operations of two types.
0 references
imbeddings
0 references