Paper Info
Title
Log-Concavity Of The Genus Polynomials Of Ringel Ladders
Abstract
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 polynomials. 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.
Year
DOI
Venue
2015
10.5614/ejgta.2015.3.2.1
ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS
Keywords
Field
DocType
genus of a graph, genus polynomial, log-concavity, partitioned genus distribution
Chebyshev polynomials,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Polynomial,Matrix (mathematics),Genus (mathematics),Conjecture,Mathematics,Algebra representation
Journal
Volume
Issue
ISSN
3
2
2338-2287
Citations 
PageRank 
References 
0
0.34
11
Authors
4
Name
Order
Citations
PageRank
Jonathan L. Gross1458268.73
Toufik Mansour242387.76
Thomas W. Tucker3191130.07
David G. L. Wang4186.52