Nowhere-zero k-flows on graphs

DOI10.1007/S00026-014-0246-5MaRDI QIDQ2256973zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 23 February 2015

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.2456

zbMATH Keywords

combinatorial reciprocity theoremgraph flowmultivariate piecewise-defined polynomialnowhere-zero flowtotally cyclic orientation

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Flows in graphs (05C21) Graph polynomials (05C31)

Abstract: We introduce and study a multivariate function that counts nowhere-zero flows on a graph G, in which each edge of G has an individual capacity. We prove that the associated counting function is a piecewise-defined polynomial in these capacities, which satisfy a combinatorial reciprocity law that incorporates totally cyclic orientations of G.

Recommendations

• The number of nowhere-zero flows on graphs and signed graphs
• Polynomials associated with nowhere-zero flows
• Nowhere-zero flow polynomials
• Polynomials counting nowhere-zero chains in graphs
• scientific article; zbMATH DE number 1874432

Cites work

• Acyclic orientations of graphs
• Ehrhart theory, modular flow reciprocity, and the Tutte polynomial
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3049182 (Why is no real title available?)
• Inside-out polytopes
• Multidimensional Ehrhart reciprocity
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• On vector partition functions
• Polynomials associated with nowhere-zero flows
• The number of nowhere-zero flows on graphs and signed graphs
• The Number of Solutions to Linear Diophantine Equations and Multivariate Splines

Cited in

(19)

• A theorem about elementary cuts and flow polynomials
• Superposition and constructions of graphs without nowhere-zero k-flows
• Polynomials associated with nowhere-zero flows
• Nowhere-zero flows in Cartesian bundles of graphs
• On (k,d)-colorings and fractional nowhere-zero flows
• Nearly nowhere-zero \(r\)-flow graphs
• scientific article; zbMATH DE number 6107212 (Why is no real title available?)
• scientific article; zbMATH DE number 1874432 (Why is no real title available?)
• Bounds of characteristic polynomials of regular matroids
• Flows on simplicial complexes
• Colorings and nowhere-zero flows of graphs in terms of Berlekamp's switching game
• scientific article; zbMATH DE number 5036077 (Why is no real title available?)
• Exponentially many nowhere-zero \(\mathbb{Z}_3\)-, \(\mathbb{Z}_4\)-, and \(\mathbb{Z}_6\)-flows
• Graph family operations
• Nowhere zero flows in line graphs
• Nowhere-zero \(k\)-flows of supergraphs
• Nowhere-zero flow polynomials
• The number of nowhere-zero flows on graphs and signed graphs
• Counting nowhere-zero flows on wheels

This page was built for publication: Nowhere-zero \(\vec{k}\)-flows on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2256973)