Tension-flow polynomials on graphs Original Research Article

An orientation of a graph is acyclic (totally cyclic) if and only if it is a “positive orientation” of a nowhere-zero integral tension (flow). We unify the notions of tension and flow and introduce the so-called tension-flows so that every orientation of a graph is a positive orientation of a nowhere-zero integral tension-flow. Furthermore, we introduce an (integral) tension-flow polynomial, which generalizes the (integral) tension and (integral) flow polynomials. For every graph G, the tension-flow polynomial FG(k1,k2) on G and the Tutte polynomial TG(k1,k2) on G satisfy FG(k1,k2)⩽TG(k1−1,k2−1). We also characterize the graphs for which the inequality is sharp.