Structure for a graph with average genus
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.
- A Kuratowski-type theorem for the maximum genus of a graph
- Determining all compact orientable 2-manifolds upon which \(K_{m,n}\) has 2-cell imbeddings
- scientific article; zbMATH DE number 951476 (Why is no real title available?)
- Kuratowski-type theorems for average genus
- Lower bounds for the average genus
This page was built for publication: Structure for a graph with average genus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2504073)
