Total embedding distributions of Ringel ladders (Q409359): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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}} | |||
Property / review text: 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}} / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Arthur T. White / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C50 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6023598 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
graph embedding | |||
Property / zbMATH Keywords: graph embedding / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Ringel ladders | |||
Property / zbMATH Keywords: Ringel ladders / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
overlap matrix | |||
Property / zbMATH Keywords: overlap matrix / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Chebyshev polynomials | |||
Property / zbMATH Keywords: Chebyshev polynomials / rank | |||
Normal rank |
Revision as of 19:12, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Total embedding distributions of Ringel ladders |
scientific article |
Statements
Total embedding distributions of Ringel ladders (English)
0 references
13 April 2012
0 references
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}}
0 references
graph embedding
0 references
Ringel ladders
0 references
overlap matrix
0 references
Chebyshev polynomials
0 references