Transversals in Trees |
| |
Authors: | Victor Campos Vašek Chvátal Luc Devroye Perouz Taslakian |
| |
Affiliation: | 1. DEPARTMENT OF COMPUTER SCIENCE, FEDERAL UNIVERSITY OF CEARá, , FORTALEZA, CE, BRAZILSupported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), Brazil.;2. CANADA RESEARCH CHAIR IN COMBINATORIAL OPTIMIZATION DEPARTMENT OF COMPUTER SCIENCE AND SOFTWARE ENGINEERING, CONCORDIA UNIVERSITY, , MONTRéAL, QUéBEC, CANADASupported by the Canada Research Chairs Program and by the Natural Sciences and Engineering Research Council of Canada.;3. SCHOOL OF COMPUTER SCIENCE, McGILL UNIVERSITY, , MONTRéAL, QUéBEC, CANADASupported by the Natural Sciences and Engineering Research Council of Canada.;4. DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITé LIBRE DE BRUXELLES, , 1050 BRUSSELS, BELGIUMPartially supported by WBI Wallonie‐Bruxelles International. |
| |
Abstract: | The total embedding polynomial of a graph G is the bivariate polynomial where is the number of embeddings, for into the orientable surface , and is the number of embeddings, for into the nonorientable surface . The sequence is called the total embedding distribution of the graph G; it is known for relatively few classes of graphs, compared to the genus distribution . The circular ladder graph is the Cartesian product of the complete graph on two vertices and the cycle graph on n vertices. In this article, we derive a closed formula for the total embedding distribution of circular ladders. |
| |
Keywords: | graph embedding total embedding distribution circular ladders overlap matrix Chebyshev polynomials |
|
|