Iterated claws have real-rooted genus polynomials

作者：Gross, Jonathan L.^*; Mansour, Toufik^*; Tucker, Thomas W.^*; Wang, David G. L.^*

来源：Ars Mathematica Contemporanea, 2016, 10(2): 255-268.

• Topological graph theory
• graph genus polynomials
• log-concavity
• real-rootedness

We prove that the genus polynomials of the graphs called iterated claws are real-rooted. This continues our work directed toward the 25-year-old conjecture that the genus distribution of every graph is log-concave. We have previously established log-concavity for sequences of graphs constructed by iterative vertex-amalgamation or iterative edge-amalgamation of graphs that satisfy a commonly observable condition on their partitioned genus distributions, even though it had been proved previously that iterative amalgamation does not always preserve real-rootedness of the genus polynomial of the iterated graph. In this paper, the iterated topological operation is adding a claw, rather than vertex- or edge-amalgamation. Our analysis here illustrates some advantages of employing a matrix representation of the transposition of a set of productions.

• 出版日期2016
• 单位北京理工大学