Genus distribution of Ringel ladders
type: Item
instance of: scholarly article
title: Genus distribution of Ringel ladders
zbMATH Open document ID: 0955.05029
DOI: 10.1016/S0012-365X(99)00250-2
author: Esther Hunt Tesar
published in: Discrete Mathematics
publication date: 2001-02-18T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 57M15
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 1455612
zbMATH Keywords: end
zbMATH Keywords: Ringel ladder
zbMATH Keywords: genus
zbMATH Keywords: genus distribution
zbMATH Keywords: connected graph
zbMATH Keywords: labelled 2-cell imbeddings
reviewed by: Arthur T. White
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1455612