Transversals in Trees |
| |
| Authors: | Victor Campos Vašek Chvátal Luc Devroye Perouz Taslakian |
| |
| Institution: | 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 ![urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0001]( "urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0001") 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 |
|
|
