Polynomials counting nowhere-zero chains in graphs
Summary: We introduce polynomials counting nowhere-zero chains in graphs -- nonhomogeneous analogues of nowhere-zero flows. For a graph \(G\), an Abelian group \(A\), and \(b:V(G)\to A\), let \(\alpha_{G,b}\) be a mapping from \(\Lambda(G)\) (a family of vertex sets of connected subgraphs of \(G\) satisfying an additional condition) to \(\{0,1\}\) 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 prove that there exists a polynomial function \(F(G,\alpha;k)\) \((\alpha=\alpha_{G,b})\) of \(k\) such that for any Abelian group \(A^\prime\) of order \(k\) and each \(b^\prime:V(G)\to A^\prime\) satisfying \(\alpha_{G,b^\prime}=\alpha\), \(F(G,\alpha;k)\) equals the number of nowhere-zero \(A^\prime\)-chains \(\varphi\) in \(G\) having boundaries equal to \(b^\prime\). In particular \(F(G,\alpha;k)\) is the flow polynomial of \(G\) if \(\alpha(X)=0\) for each \(X\in\Lambda(G)\). Finally we characterize \(\alpha\) for which \(F(G,\alpha;k)\) is nonzero and show that in this case \(F(G,\alpha;k)\) has the same degree as the flow polynomial of \(G\).
- Zeros of graph-counting polynomials
- Chain polynomials of graphs
- Zeros of chromatic and flow polynomials of graphs
- Combinatorics of polynomial chains
- On sequences of polynomials arising from graph invariants
- Polynomial graph invariants from homomorphism numbers
- Polynomial graph invariants from homomorphism numbers
- Location of Zeros of Chromatic and Related Polynomials of Graphs
- Fubini numbers and polynomials of graphs
- Polynomial sequences of binomial-type arising in graph theory
- A Contribution to the Theory of Chromatic Polynomials
- Chromatic polynomials
- Ehrhart theory, modular flow reciprocity, and the Tutte polynomial
- Enumerating colorings, tensions and flows in cell complexes
- Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties
- scientific article; zbMATH DE number 437298 (Why is no real title available?)
- scientific article; zbMATH DE number 5657441 (Why is no real title available?)
- scientific article; zbMATH DE number 4027488 (Why is no real title available?)
- scientific article; zbMATH DE number 67324 (Why is no real title available?)
- Inside-out polytopes
- Integer flows and orientations
- Interpretations of the Tutte and characteristic polynomials of matroids
- Nowhere-zero 3-flows and modulo \(k\)-orientations
- Orientations, lattice polytopes, and group arrangements. II: Modular and integral flow polynomials of graphs
- Superposition and constructions of graphs without nowhere-zero k-flows
- The Tutte-Potts connection in the presence of an external magnetic field
- Unsolved graph colouring problems
This page was built for publication: Polynomials counting nowhere-zero chains in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2073314)
