Contents Online

# Journal of Combinatorics

## Volume 7 (2016)

### Number 2–3

Guest editors: Rong Luo and Cun-Quan Zhang

### The matrix cover polynomial

Pages: 375 – 412

DOI: http://dx.doi.org/10.4310/JOC.2016.v7.n2.a9

#### Authors

#### Abstract

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