The matrix cover polynomial

The cover polynomial $C(D) = C(D; x, y)$ of a digraph $D$ is a two-variable polynomial whose coefficients are determined by the number of vertex coverings of $D$ by directed paths and cycles. Just as for the Tutte polynomial for undirected graphs, various properties of $D$ can be read off from the values of $C(D; x, y)$. For example, for an $n$-vertex digraph $D, C(D; 1, 0)$ is the number of Hamiltonian paths in $D, C(D; 0, 1)$ is the permanent of adjacency matrix of $D$, and $C(D; 0, -1)$ is $(-1)^n$ times the determinant of the adjacency matrix of $D$. In this paper, we extend these ideas to a much more general setting, namely, to matrices with elements taken from an arbitrary commutative ring with identity. In particular, we establish a reciprocity theorem for this generalization, as well as establishing a symmetric function version of the new polynomial, similar in spirit to Stanley’s symmetric function generalization of the chromatic polynomial of a graph, and Tim Chow’s symmetric function generalization of the usual cover polynomial. We also show that all of the generalized polynomials and symmetric functions can also be obtained by a deletion/contraction process.

Keywords

digraph polynomials, Tutte polynomials, deletion/contraction rules

Full Text (PDF format)

Published 23 February 2016