Recurrences for the genus polynomials of linear sequences of graphs

Rok, strany: 2020, 505 - 526

Given a finite graph $H$, the $n\uth$ member $G_n$ of an \textit{$H$-linear sequence} is obtained recursively by attaching a disjoint copy of $H$ to the last copy of $H$ in $G_n-1$ by adding edges or identifying vertices, always in the same way. The \textit{genus polynomial} $Γ_G(z)$ of a graph $G$ is the generating function enumerating all orientable embeddings of $G$ by genus. Over the past 30 years, most calculations of genus polynomials $Γ_Gn(z)$ for the graphs in a linear family have been obtained by partitioning the embeddings of $G_n$ into types $1,2,…,k$ with polynomials $Γ_Gn^j(z)$, for $j=1,2,…,k$; from these polynomials, we form a column vector $V_n(z) = [Γ_Gn¹(z), Γ_Gn²(z), …, Γ_Gn^k(z)]^t$ that satisfies a recursion $V_n(z) = M(z)V_n-1(z)$, where $M(z)$ is a $k× k$ matrix of polynomials in $z$. In this paper, the Cayley-Hamilton theorem is used to derive a $k\uth$ degree linear recursion for $Γ_n(z)$, allowing us to avoid the partitioning, thereby yielding a reduction from $k²$ multiplications of polynomials to $k$ such multiplications. Moreover, that linear recursion can facilitate proofs of real-rootedness and log-concavity of the polynomials. We illustrate with examples.

ISO 690:

Chen, Y., Gross, J., Mansour, T., Tucker, T. 2020. Recurrences for the genus polynomials of linear sequences of graphs. In Mathematica Slovaca, vol. 70, no.3, pp. 505-526. 0139-9918. DOI: https://doi.org/10.1515/ms-2017-0368

APA:

Chen, Y., Gross, J., Mansour, T., Tucker, T. (2020). Recurrences for the genus polynomials of linear sequences of graphs. Mathematica Slovaca, 70(3), 505-526. 0139-9918. DOI: https://doi.org/10.1515/ms-2017-0368

Vydavateľ: Mathematical Institute, Slovak Academy of Sciences, Bratislava