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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references