Generalized bicycles
type: Item
instance of: scholarly article
title: Generalized bicycles
zbMATH Open document ID: 0887.05049
DOI: 10.1016/S0166-218X(97)00013-9
author: Kenneth A. Berman
author: Yanpei Liu
published in: Discrete Applied Mathematics
publication date: 1998-04-28T00:00:00Z
full work available at URL: dam
review text: Let \(G=(V,E)\) be a graph with \(n\) vertices, and let \(M\) be a (left) modul over a principal ideal domain \(D\). Let \(W_0(M)\) and \(W_1(M)\) denote the modules of all vertex and edge weightings over \(M\), respectively. An incidence weighting \(\eta\) of \(G\) is a weighting of each incident vertex-edge pair \((v, e)\) with an element of \(D\). Consider an orientation of the edges of \(G\). Denote \(\delta_{\eta}\) the linear operator from \(W_0(M)\) to \(W_1(M)\) given by \(\delta_{\eta}(w)(e)= \eta (u, e)w(u)-\eta (v,e)w(v)\), where \(e\in E\) and \(u\) and \(v\) denote the tail and head of \(e\), respectively. An \({\eta}\)-cocycle is a weighting \(c\in W_1(M)\), such that \(c=\delta (w)\) for some \(w\in W_0(M)\). An \(\eta\)-bicycle is an \(\eta\)-cocycle that is also a cycle (ordinary bicycles are obtained when \(\eta\equiv 1)\). Denote \(B_{\eta}(M)\) the module of all vertex weightings \(b\in W_0(M)\), such that \(\delta_{\eta}(b)\) is an \(\eta\)-bicycle. For \(T\) a spanning tree rooted at vertex \(v\), let \(\eta (T)\) denote the product of \(\eta (u, e)\) over all the edges \(e\) of \(T\), where \(u\) denotes the end vertex of \(e\) that is further from \(v\) in \(T\). The \(\eta\)-complexity \(\tau_{\eta}\) of \(G\) is the vertex weighting over \(D\), such that \(\tau_{\eta}(v)\) is the sum of \(\eta (T)\) over all spanning trees \(T\) rooted at \(v\). The gdc \({\eta}\)-complexity \(t_{\eta}\) is the greatest common divisor of \(\{\tau_{\eta}(v): v\in V\}\). It is proved that \(t_{\eta}\) has a factorization \(t_{\eta}=t_1t_2\dots t_{n-1}\), unique up to multiplication by units of \(D\), such that \(t_{i+1}\) divides \(t_i\) and such that for every module \(M\) over \(D\), \(B_{\eta}(M)\) is isomorphic to the direct sum of \(M\) and the submodules \(M(T_i)= \{m\in M: t_im=0\}, i=1,\dots ,n-1\). (Theorem 2.1). Further, it is proved that \(B_{\eta}(M)\cong M\) if and only if \(\tau_{\eta}m\) is nonzero for every nonzero \(m\in M\). If \(B_{\eta}(M)…
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 1109931
zbMATH Keywords: graph theory
zbMATH Keywords: generalized bicycles
zbMATH Keywords: cocycles
zbMATH Keywords: incidence weighting graph
reviewed by: Lubomír Bakule
MaRDI profile type: Publication
cites work: A Graph Theoretical Approach to Handicap Ranking of Tournaments and Paired Comparisons
cites work: Leaky Electricity: 1-Chain Formulas for the Current and Voltage
cites work: Bicycles and Spanning Trees
cites work: Balanced vertex weightings and arborescences
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: Q3706275
cites work: Q4771385
cites work: A polyhedral theory on graphs
cites work: Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs
cites work: Q5585910
cites work: On Generalized Tournament Matrices
cites work: On the Principal Edge Tripartition of a Graph
cites work: Graph property recognition machines
cites work: Q4063182
cites work: Q5786986
cites work: Q5607111
OpenAlex ID: W2913827139
description: scientific article; zbMATH DE number 1109931