Spanning Forests of a Digraph and Their Applications
<|reference_start|>Spanning Forests of a Digraph and Their Applications: 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.<|reference_end|>
@article{agaev2006spanning,
    title={Spanning Forests of a Digraph and Their Applications},
    author={Rafig Agaev and Pavel Chebotarev},
    journal={Automation and Remote Control 62 (2001) No.3 443-466},
    year={2006},
    doi={10.1023/A:1002862312617},
    archivePrefix={arXiv},
    eprint={math/0602061},
    primaryClass={math.CO cs.DM math.RA}
}