Genus distribution of Ringel ladders (Q1567280)

The closed end ladder \(L_n\) results from the Cartesian product \(K_2\times P_n\) by doubling each end rung; the Ringel ladder \(R_n\) results from \(L_n\) by subdividing one of the two rungs at each end and then joining the two new vertices by an edge. These graphs underlie current graphs used in finding the genus of the complete graphs; see, for example, \textit{G. Ringel} [Map color theorem (Springer-Verlag, Berlin) (1974; Zbl 0287.05102)]. The genus distribution of a connected graph \(G\) is given by the numbers \(g_k(G)=\) the number of labelled 2-cell imbeddings of \(G\) on the closed orientable 2-manifold of genus \(k\), where \(k\) ranges from the genus of \(G\) to the maximum genus of \(G\). \textit{M. L. Furst}, \textit{J. L. Gross} and \textit{R. Statman} [J. Comb. Theory, Ser. B 46, No. 1, 22-36 (1989; Zbl 0669.05028)] found the genus distribution for \(L_n\). The present author does the same for \(R_n\) and then calculates the average genus for \(R_n\), over all \(2^{2n+2}\) labelled 2-cell imbeddings. (This is the expected value of the genus random variable for \(R_n\), assuming the uniform probability distribution.) A corollary is that the average genus is not asymptotic to the maximum genus for \(R_n\) (whereas it is so, for the complete graph \(K_n\); see the reviewer [Comb. Probab. Comput. 3, No. 4, 545-555 (1994; Zbl 0815.05027)].