Generalized matrix tree theorem for mixed graphs

Abstract

In this article we provide a combinatorial description of an arbitrary minor of the Laplacian matrix (L) of a mixed graph (a graph with some oriented and some unoriented edges). This is a generalized Matrix Tree Theorem. We also characterize the non-singular substructures of a mixed graph. The sign attached to a nonsingular substructure is described in terms of labeling and the number of unoriented edges included in certain paths. Nonsingular substructures may be viewed as generalized matchings, because in the case of disjoint vertex sets corresponding to the rows and columns of a minor of L, our generalized Matrix Tree Theorem provides a signed count over matchings between those vertex sets. A mixed graph is called quasi bipartite if it does not contain a non singular cycle (a cycle containing an odd number of un-oriented edges). We give several characterizations of quasi-bipartite graphs.