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: https://dx.doi.org/10.4310/JOC.2016.v7.n2.a9

Authors

Fan Chung (University of California at San Diego, La Jolla, Calif.)

Ron Graham (University of California at San Diego, La Jolla, Calif.)

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

Published 23 February 2016