Total embedding distributions of Ringel ladders (Q409359): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(7 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Yi-Chao Chen / rank | |||
Property / author | |||
Property / author: Yi-Chao Chen / rank | |||
Normal rank | |||
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 | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1995600137 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1011.3869 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3822182 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Overlap matrices and total imbedding distributions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The total embedding distributions of cacti and necklaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Embedding distributions and Chebyshev polynomials / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Embedding Distributions of Generalized Fan Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Genus distributions for two classes of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Triangular embeddings of complete graphs from graceful labellings of paths / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hierarchy for imbedding-distribution invariants of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3094521 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Genus distributions for bouquets of circles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2732568 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Exponential families of non-isomorphic non-triangular orientable genus embeddings of complete graphs. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Total embedding distributions for bouquets of circles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The semi-arc automorphism group of a graph with application to map enumeration / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An obstruction to embedding graphs in surfaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2726740 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lower bound of the number of maximum genus embeddings and genus embeddings of \(K_{12s+7}\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4773723 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3997537 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Region distributions of graph embeddings and Stirling numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Region distributions of some small diameter graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Generalized Embedding Schemes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Genus distribution of Ringel ladders / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The graph genus problem is NP-complete / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Census of Planar Maps / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Orientable embedding genus distribution for certain types of graphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 02:22, 5 July 2024
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
0 references
0 references