On the average genus of a graph (Q2366954)

The average genus of a fixed connected graph \(G\) is the average value of the genus of the imbedding surface, taken over all labelled orientable 2- cell imbeddings of \(G\). Thus if \(G\) has degree sequence \(\{d_ 1,d_ 2,\dots,d_ p\}\), the average genus of \(G\) is the expected value of the genus random variable on the sample space of all \(\prod^ p_{i=1}(d_ i-1)!\) labelled orientable 2-cell imbeddings of \(G\), with the uniform distribution. Not all nonnegative rational numbers occur as values for this random variable, as \(G\) varies; it is shown that the six smallest positive values are 1/3, 1/2, 5/9, 2/3, 19/27, and 3/4. A ``necklace of type \((r,s)\)'' is shown to have average genus \(1-(1/2)^ r(2/3)^ s\), from which three corollaries follow: (1) Arbitrarily many mutually nonhomeomorphic 2-connected graphs can have the same average genus. (2) The average genus of a graph with nontrivial genus range can lie arbitrarily close to the maximum genus (which is 1, for these necklaces). (3) The number 1 is an upper limit point of the set of possible values of average genus. It is also shown that the only 3-connected graph whose average genus is less than 1 is \(K_ 4\) (which has average genus 7/8).