2018/05/21 by Jianguo Qian, Qian, Jianguo · 1 citation
Computer Science · Mathematics · #05C21 #05C22 #05C31 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1805.07878
openalex publication_date 2018/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In contrast to ordinary graphs, the number of the nowhere-zero group-flows in a signed graph may vary with different groups, even if the groups have the same order. In fact, for a signed graph G and non-negative integer d, it was shown that there exists a polynomial Fd(G,x) such that the number of the nowhere-zero Γ-flows in G equals Fd(G,x) evaluated at k for every Abelian group Γ of order k with ε(Γ)=d, where ε(Γ) is the largest integer d for which Γ has a subgroup isomorphic to ℤd2. We focus on the combinatorial structure of Γ-flows in a signed graph and the coefficients in Fd(G,x). We first define the fundamental directed circuits for a signed graph G and show that all Γ-flows (not necessarily nowhere-zero) in G can be generated by these circuits. It turns out that all Γ-flows in G can be evenly classified into 2ε(Γ)-classes specified by the elements of order 2 in Γ, each class of which consists of the same number of flows depending only on the order of the group. This gives an explanation for why the number of Γ-flows in a signed graph varies with different ε(Γ), and also gives an answer to a problem posed by Beck and Zaslavsky. Secondly, using an extension of Whitney's broken circuit theory we give a combinatorial interpretation of the coefficients in Fd(G,x) for d=0, in terms of the broken bonds. As an example, we give an analytic expression of F0(G,x) for a class of the signed graphs that contain no balanced circuit. Finally, we show that the sets of edges in a signed graph that contain no broken bond form a homogeneous simplicial complex.