Flow polynomials of a signed graph (Q2323814)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Flow polynomials of a signed graph |
scientific article |
Statements
Flow polynomials of a signed graph (English)
0 references
12 September 2019
0 references
Summary: For a signed graph \(G\) and non-negative integer \(d\), it was shown by \textit{M. DeVos} et al. [Electron. J. Comb. 26, No. 2, Research Paper P2.38, 7 p. (2019; Zbl 1441.05096)] that there exists a polynomial \(F_d(G,x)\) such that the number of the nowhere-zero \(\Gamma\)-flows in \(G\) equals \(F_d(G,x)\) evaluated at \(k\) for every Abelian group \(\Gamma\) of order \(k\) with \(\epsilon(\Gamma)=d\), where \(\epsilon(\Gamma)\) is the largest integer \(d\) for which \(\Gamma\) has a subgroup isomorphic to \(\mathbb{Z}^d_2\). We define a class of particular directed circuits in \(G\), namely the fundamental directed circuits, and show that all \(\Gamma\)-flows (not necessarily nowhere-zero) in \(G\) can be generated by these circuits. It turns out that all \(\Gamma\)-flows in \(G\) can be evenly partitioned into \(2^{\epsilon(\Gamma)}\) classes specified by the elements of order 2 in \(\Gamma\), each class of which consists of the same number of flows depending only on the order of \(\Gamma\). Using an extension of Whitney's broken circuit theorem of Dohmen and Trinks, we give a combinatorial interpretation of the coefficients in \(F_d(G,x)\) for \(d=0\) in terms of broken bonds. Finally, we show that the sets of edges in a signed graph that contain no broken bond form a homogeneous simplicial complex.
0 references
nowhere-zero \(\Gamma\)-flows
0 references
fundamental directed circuits
0 references