Log-concavity of the genus polynomials of Ringel Ladders

Jonathan L Gross (Columbia University)
Toufik Mansour (Department of Mathematics, University of Haifa, 3498838 Haifa, Israel)
Thomas W. Tucker (Departments of Mathematics, Colgate University, Hamilton, NY 13346, USA)
David G.L. Wang (School of Mathematics and Statistics, Beijing Institute of Technology, 102488, P.R. China)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 3, No 2 (2015): Electronic Journal of Graph Theory and Applications

A Ringel ladder can be formed by a self-bar-amalgamation operation on a symmetric ladder, that is, by joining the root vertices on its end-rungs. The present authors have previously derived criteria under which linear chains of copies of one or more graphs have log-concave genus polyno- mials. Herein we establish Ringel ladders as the first significant non-linear infinite family of graphs known to have log-concave genus polynomials. We construct an algebraic representation of self-bar-amalgamation as a matrix operation, to be applied to a vector representation of the partitioned genus distribution of a symmetric ladder. Analysis of the resulting genus polynomial involves the use of Chebyshev polynomials. This paper continues our quest to affirm the quarter-century-old conjecture that all graphs have log-concave genus polynomials.