Counting Flows of $b$-compatible Graphs

Abstract

Kochol introduced the assigning polynomial $F(G,\alpha ;k)$ to count nowhere-zero $(A,b)$-flows of a graph $G$, where $A$ is a finite Abelian group and $\alpha$ is a $\{0,1\}$-assigning from a family $\Lambda (G)$ of certain nonempty vertex subsets of $G$ to $\{0,1\}$. We introduce the concepts of $b$-compatible graph and $b$-compatible broken bond to give an explicit formula for the assigning polynomials and to examine their coefficients. More specifically, for a function $b:V(G)\to A$, let ${\alpha }_{G,b}$ be a $\{0,1\}$-assigning of $G$ such that for each $X\in \Lambda (G)$, ${\alpha }_{G,b}(X)=0$ if and only if ${\sum }_{v\in X}b(v)=0$. We show that for any $\{0,1\}$-assigning $\alpha$ of $G$, if there exists a function $b:V(G)\to A$ such that $G$ is $b$-compatible and $\alpha ={\alpha }_{G,b}$, then the assigning polynomial $F(G,\alpha ;k)$ has the $b$-compatible spanning subgraph expansion \[ F(G,α;k)=\sum_{\substack{S\subseteq E(G),\\G-S\mbox{ is $b$-compatible}}}(-1)^{|S|}k^{m(G-S)}, \] and is the following form $F(G,\alpha ;k)={\sum }_{i=0}^{m(G)}(-1{)}^i{a}_i(G,\alpha )k^{m(G)-i}$, where each $a_i(G,\alpha )$ is the number of subsets $S$ of $E(G)$ having $i$ edges such that $G-S$ is $b$-compatible and $S$ contains no $b$-compatible broken bonds with respect to a total order on $E(G)$. Applying the counting interpretation, we also obtain unified comparison relations for the signless coefficients of assigning polynomials. Namely, for any $\{0,1\}$-assignings $\alpha ,{\alpha }^{\prime }$ of $G$, if there exist functions $b:V(G)\to A$ and $b^{\prime }:V(G)\to A^{\prime }$ such that $G$ is both $b$-compatible and $b^{\prime }$-compatible, $\alpha ={\alpha }_{G,b}$, ${\alpha }^{\prime }={\alpha }_{G,b^{\prime }}$ and $\alpha (X)\le {\alpha }^{\prime }(X)$ for all $X\in \Lambda (G)$, then \[ a_i(G,α)\le a_i(G,α') \quad \mbox{ for }\quad i=0,1,\ldots, m(G). \]

12pages