Spanning Forests of a Digraph and Their Applications

Details Spanning Forests of a Digraph and Their Applications Spanning Forests of a Digraph and Their Applications

2006-02-03

arxiv.org/abs/math/0602061v1

Automation and Remote Control 62 (2001) No.3 443-466

Mathematics

Combinatorics

24 pages

Scientific paper

10.1023/A:1002862312617

We study spanning diverging forests of a digraph and related matrices. It is shown that the normalized matrix of out forests of a digraph coincides with the transition matrix in a specific observation model for Markov chains related to the digraph. Expression are given for the Moore-Penrose generalized inverse and the group inverse of the Kirchhoff (Laplacian) matrix. These expressions involve the matrix of maximum out forest of the digraph. Every matrix of out forests with a fixed number of arcs and the normalized matrix of out forests are represented as polynomials in the Kirchhoff matrix; with the help of these identities new proofs are given for the matrix-forest theorem and some other statements. A connection is specified between the forest dimension of a digraph and the degree of an annihilating polynomial for the Kirchhoff (Laplacian) matrix. Some accessibility measures for digraph vertices are considered. These are based on the enumeration of spanning forests.

Affiliated with

Also associated with

No associations

Rating

Spanning Forests of a Digraph and Their Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spanning Forests of a Digraph and Their Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning Forests of a Digraph and Their Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-485132