Tension-flow polynomials on graphs |
| |
Institution: | MÚ SAV, Štefánikova 49, 814 73 Bratislava 1, Slovakia |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|