Generalized bicycles
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)\cong M\) then \(B_{\eta}(M)= \{\tau_{\eta}m: m\in M\}\) (Theorem 3.1). Particular results about bicycles, balanced vertex weightings, resistive and leaky electical networks, handicap ranking of tournaments, and Markov chains are obtained as special cases of this formula.
scientific article; zbMATH DE number 1109931
scientific article