Generalized matrix tree theorem for mixed graphs

Bapat, Ravindra B. ; Grossman, Jerrold W. ; Kulkarni, Devadatta M. (1999) Generalized matrix tree theorem for mixed graphs Linear and Multilinear Algebra, 46 (4). pp. 299-312. ISSN 1563-5139

Full text not available from this repository.

Official URL:

Related URL:


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.

Item Type:Article
Source:Copyright of this article belongs to Taylor and Francis Group.
Keywords:Generalized Matching; Laplacian; Matrix Tree Theorem; Mixed Graph; Non-singular Substructure; Quasi-bipartite Graph; K-reduced Spanning Substructure; Ams Subject; Classifications (1991): Primary: 05C50; Secondary: 15A15, 05C30, 05C70
ID Code:77803
Deposited On:14 Jan 2012 15:25
Last Modified:14 Jan 2012 15:25

Repository Staff Only: item control page