Log-concavity of the Genus Polynomials of Ringel Ladders
2015
Jonathan L. Gross, Toufik Mansour, Thomas W. Tucker, David G. L. Wang

Metrik

  • Eye Icon 204 kali dilihat
  • Download Icon 96 downloads
Metrics Icon 204 kali dilihat  //  96 downloads
Abstrak

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.

Full text
Show more arrow
 
More from this journal
Intersecting Longest Paths and Longest Cycles: a Survey
The Complete List of Ramsey $(2K_2,K_4)$-minimal Graphs
🧐  Browse all from this journal

Metrik

  • Eye Icon 204 kali dilihat
  • Download Icon 96 downloads
Metrics Icon 204 kali dilihat  //  96 downloads