Journal of Combinatorics

Volume 5 (2014)

Number 2

Log-concavity of the genus polynomials for a sequence of cubic Halin graphs

Pages: 203 – 233

DOI: https://dx.doi.org/10.4310/JOC.2014.v5.n2.a4

Authors

Jonathan L. Gross (Department of Computer Science, Columbia University, New York, N.Y., U.S.A.)

Toufik Mansour (Department of Mathematics, University of Haifa, Israel)

Thomas W. Tucker (Department of Mathematics, Colgate University, Hamilton, New York, U.S.A.)

Abstract

A Halin graph is a graph obtained from a plane tree by running a cycle through its leaf vertices in the order they are encountered along a counterclockwise pre-order traversal. Using a vectorized production matrix, we give a matrix formula for the partitioned genus polynomial of any cubic Halin graph and for the genus polynomial as well. We prove log-concavity of the genus polynomial and of the partitioned genus polynomials for several sequences of cubic Halin graphs, which serves as further support of the conjecture that the genus polynomial of every graph is log-concave.

Published 20 August 2014