Balanced vertex weightings and arborescences (Q1108289)

Let D be a digraph with vertex set V and let \((\Gamma,+,0)\) be any Abelian group. A weighting b of the vertices with elements of \(\Gamma\) is balanced if for every vertex v the weight on v is ``the average'' of the weights on the vertices in the out-neighborhood of v, i.e., \(d^+(v)b(v)=\sum b(w)\) where the summation is over all vertices w in the outneighborhood of v and \(d^+(v)\) denotes the out-degree of v. The set B(\(\Gamma)\) of all balanced vertex weightings determines a group. Let \(a_ v\) denote the number of spanning in arborescences rooted at vertex v and let \(\alpha =\gcd \{a_ v| v\in V\}\). In this paper we show that \(\alpha\) has a unique factorization \(\alpha =\alpha_ 1\alpha_ 2...\alpha_ m\) such that \(\alpha_ i\) is a multiple of \(\alpha_{i+1}\), \(i=1,2,...,m-1\) and such that for every Abelian group \(\Gamma\), \(B(\Gamma)\cong \Gamma \times \Gamma (a_ 1)\times...\times \Gamma (\alpha_ m)\), where \(\Gamma (\alpha_ i)=\{g\in \Gamma | \alpha_ ig=0\}\). As a corollary, we obtain the characterization of the group of bicycles over \(\Gamma\) given in [the author, SIAM J. Algebraic Discrete Methods 7, 1-12 (1986; Zbl 0588.05016)]. We also obtain many results about the arborescence numbers including a new proof of Tutte's trinity theorem and two formulae for \(a_ v\).