Balanced vertex weightings and arborescences
type: Item
instance of: scholarly article
title: Balanced vertex weightings and arborescences
zbMATH Open document ID: 0654.05040
DOI: 10.1016/0095-8956(87)90046-3
published in: Journal of Combinatorial Theory. Series B
publication date: 1987-01-01T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 4066931
zbMATH Keywords: digraph
zbMATH Keywords: Abelian group
zbMATH Keywords: weighting
zbMATH Keywords: balanced vertex weightings
zbMATH Keywords: arborescence numbers
zbMATH Keywords: Tutte's trinity theorem
author: Kenneth A. Berman
MaRDI profile type: Publication
full work available at URL: 0095-8956(87)90046-3
OpenAlex ID: W1971892699
cites work: A Proof of Tuite’s Trinity Theorem and a New Determinant Formula
cites work: Leaky Electricity: 1-Chain Formulas for the Current and Voltage
cites work: Bicycles and Spanning Trees
cites work: A Combinatorial Proof of the All Minors Matrix Tree Theorem
cites work: On Vector Spaces Associated with a Graph
cites work: Q4088840
cites work: Q4771385
cites work: Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs
cites work: On the Principal Edge Tripartition of a Graph
cites work: Graph property recognition machines
cites work: Q5786986
cites work: Q4065567
cites work: Q4099666
cites work: Rotors in Graph Theory
description: scientific article; zbMATH DE number 4066931