Flow polynomials of a signed graph

Xiangyu Ren ; Jianguo Qian¹

¹Xiamen university

The electronic journal of combinatorics, Tome 26 (2019) no. 3

Résumé

For a signed graph $G$ and non-negative integer $d$, it was shown by DeVos et al. 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.

Détail

DOI : 10.37236/8226

Classification : 05C21, 05C22, 05C31
Mots-clés : nowhere-zero \(\Gamma\)-flows, fundamental directed circuits