Spanning Forests of a Digraph and Their Applications

Simple item page
dc.creatorAgaev, Rafig
dc.creatorChebotarev, Pavel
dc.date2006-02-03
dc.date.accessioned2026-07-07T07:03:05Z
dc.date.available2026-07-07T07:03:05Z
dc.descriptionWe 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.
dc.description24 pages
dc.identifierhttps://arxiv.org/abs/math/0602061
dc.identifierhttp://arxiv.org/abs/math/0602061
dc.identifierAutomation and Remote Control 62 (2001) No.3 443-466
dc.identifierdoi:10.1023/A:1002862312617
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/108842
dc.subjectCombinatorics
dc.subjectDiscrete Mathematics
dc.subjectRings and Algebras
dc.subject05C50; 05C05; 15A51
dc.titleSpanning Forests of a Digraph and Their Applications
dc.typetext

Files

Collections

arXiv