Genus distribution of Ringel ladders

DOI10.1016/S0012-365X(99)00250-2MaRDI QIDQ1567280zbMATH OpenFDO

Authors Esther Hunt Tesar

Publication date 18 February 2001

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(99)00250-2

zbMATH Keywords

connected graphendgenusgenus distributionlabelled 2-cell imbeddingsRingel ladder

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15)

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)].

Recommendations

• Total embedding distributions of Ringel ladders
• scientific article; zbMATH DE number 1789783
• Genus distribution of ladder type and cross type graphs
• Genus distributions for several types of ladder-class graphs

Cited in

(28)

• On the embedding genus distribution of ladders and crosses
• Genus distribution of ladder type and cross type graphs
• Genus distributions for two classes of graphs
• Embedding distributions and Chebyshev polynomials
• Nordhaus-Gaddum results for genus
• Enumerating reflexible 2-cell embeddings of connected graphs
• Genus distributions for several types of ladder-class graphs
• Limit for the Euler-genus distributions of ladder-like sequences of graphs
• Genus polynomials of cycles with double edges
• Orientable embedding genus distribution for certain types of graphs
• The genus distributions of directed antiladders in orientable surfaces
• The genus distributions for a certain type of permutation graphs in orientable surfaces
• The semi-arc automorphism group of a graph with application to map enumeration
• The total embedding distributions of cacti and necklaces
• Genera of Cayley maps
• Total embedding distributions of Ringel ladders
• Genus distribution of \(P_3 \mathop\square P_n\)
• scientific article; zbMATH DE number 1789783 (Why is no real title available?)
• Genus distributions of star-ladders
• Log-concavity of the genus polynomials of Ringel ladders
• Enumerating graph embeddings and partial-duals by genus and Euler genus
• Topological Graph Theory: A Personal Account
• scientific article; zbMATH DE number 5584119 (Why is no real title available?)
• Counting orientable embeddings by genus for a type of 3-regular graph
• Strong log-convexity of genus sequences
• Region distributions of graph embeddings and Stirling numbers
• The genus polynomials of cross-ladder digraphs in orientable surfaces
• Number of embeddings of circular and Möbius ladders on surfaces

This page was built for publication: Genus distribution of Ringel ladders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1567280)