Embedding Distributions and Chebyshev Polynomials

摘要

The history of genus distributions began with J. Gross et al. in 1980s. Since then, a lot of study has given to this parameter, and the explicit formulas are obtained for various kinds of graphs. In this paper, we find a new usage of Chebyshev polynomials in the study of genus distribution, using the overlap matrix, we obtain homogeneous recurrence relation for rank distribution polynomial, which can be solved in terms of Chebyshev polynomials of the second kind. The method here can find explicit formula for embedding distribution of some other graphs. As an application, the well known genus distributions of closed-end ladders and cobblestone paths (Furst et al. in J Combin Ser B 46:22–36, 1989) are derived. The explicit formula for non-orientable embedding distributions of closed-end ladders and cobblestone paths are also obtained.