Total embedding distributions of Ringel ladders (Q409359): Difference between revisions

The \(n\)-rung closed-end ladder \(L_n\) arises by starting with the Cartesian product \(K_2 \times P_n\), and then doubling both end rungs. The Ringel ladder \(R_n\) follows from \(L_n\) by performing an elementary subdivision on each of the two new end rungs, and then adding an edge to join these two new vertices. These ladders (for \(n\) even) form the current graphs for case 7 of the complete graph theorem. (See, for example, \textit{G. Ringel}, Map color theorem. Die Grundlehren der mathematischen Wissenschaften. 209. Berlin-Heidelberg-New York: Springer-Verlag (1974; Zbl 0287.05102).) For a connected graph \(G\), the genus distribution is a sequence \(g_i\), as \(i\) ranges from the genus of \(G\) to the maxium genus of \(G\), where each \(g_i\) records the number of labeled 2-cell imbeddings of \(G\) on the closed orientable 2-manifold of genus \(i\). For example, \(R_1\) is just \(K_4\), for which \(g_0= 2\) and \(g_1=14\). \textit{E.H. Tesar} [``Genus distribution of Ringel ladders,'' Discrete Math. 216, No. 1--3, 235--252 (2000; Zbl 0955.05029)] calculated the genus distribution of \(R_n\), using a combinatorial approach building upon the genus distribution of \(L_n\) [\textit{M. L. Furst}, \textit{J. L. Gross} and \textit{R. Statman}, ``Genus distributions for two classes of graphs,'' J. Comb. Theory, Ser. B 46, No. 1, 22--36 (1989; Zbl 0669.05028)]. The present authors use overlap matrices and Chebyshev polynomials of the second kind to {\parindent=7mm \begin{itemize}\item[(1)]re-calculate the Tesar results, \item[(2)]obtain an explicit formula for the corresponding numbers of non-orientable imbeddings for Ringel ladders, and hence \item[(3)]combine, to determine the total imbedding distribution of Ringel ladders. \end{itemize}}