Generalized matrix tree theorem for mixed graphs
- 1 October 1999
- journal article
- research article
- Published by Taylor & Francis in Linear and Multilinear Algebra
- Vol. 46 (4) , 299-312
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.Keywords
This publication has 4 references indexed in Scilit:
- On the minors of an incidence matrix and its Smith normal formLinear Algebra and its Applications, 1995
- Laplacian matrices of graphs: a surveyLinear Algebra and its Applications, 1994
- A Combinatorial Proof of the All Minors Matrix Tree TheoremSIAM Journal on Algebraic Discrete Methods, 1982
- Graph Theory with Applications1976