✦ LIBER ✦

The Algebra of Flows in Graphs

✍ Scribed by David G Wagner

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 452 KB
Volume: 21
Category: Article
ISSN: 0196-8858
DOI: 10.1006/aama.1998.0610

No coin nor oath required. For personal study only.

✦ Synopsis

We define a contravariant functor K from the category of finite graphs and graph morphisms to the category of finitely generated graded abelian groups and homomorphisms. For a graph X, an abelian group B, and a nonnegative integer j, Ž j Ž . . an element of Hom K X , B is a coherent family of B-valued flows on the set of Ž . all graphs obtained by contracting some j y 1 -set of edges of X; in particular, Ž 1 Ž . . Ž . и Ž . Hom K X , ‫ޒ‬ is the familiar real ''cycle-space'' of X. We show that K X is ny k Ž torsion-free and that its Poincare polynomial is the specialization t T 1rt, ´X . Ž . 1 q t of the Tutte polynomial of X here X has n vertices and k components . и и Ž . Functoriality of K induces a functorial coalgebra structure on K X ; dualizing, Ž и Ž . . for any ring B we obtain a functorial B-algebra structure on Hom K X , B . When B is commutative we present this algebra as a quotient of a divided power algebra, leading to some interesting inequalities on the coefficients of the above Poincare polynomial. We also provide a formula for the theta function of the ĺattice of integer-valued flows in X, and conclude with 10 open problems.

📜 SIMILAR VOLUMES

NZ-flows in strong products of graphs

✍ Wilfried Imrich; Iztok Peterin; Simon Špacapan; Cun-Quan Zhang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB

We prove that the strong product G 1 G 2 of G 1 and G 2 is Z 3 -flow contractible if and only if G 1 G 2 is not T K 2 , where T is a tree (we call T K 2 a K 4 -tree). It follows that G 1 G 2 admits an NZ 3-flow unless G 1 G 2 is a K 4 -tree. We also give a constructive proof that yields a polynomial

Nowhere-Zero Flows in Random Graphs

✍ Benny Sudakov 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 138 KB

A nowhere-zero 3-flow in a graph G is an assignment of a direction and a value of 1 or 2 to each edge of G such that, for each vertex v in G, the sum of the values of the edges with tail v equals the sum of the values of the edges with head v. Motivated by results about the region coloring of planar

Tight Distance-regular Graphs and the Su

Tight Distance-regular Graphs and the Subconstituent Algebra

✍ Junie T. Go; Paul Terwilliger 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 427 KB

Nowhere-zero flows in tensor product of

Nowhere-zero flows in tensor product of graphs

✍ Zhao Zhang; Yirong Zheng; Aygul Mamut 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB 👁 1 views

## Abstract In this paper, we characterize graphs whose tensor product admit nowhere‐zero 3‐flow. The main result is: For two graphs __G__~1~ and __G__~2~ with δ ≥ 2 and __G__~2~ not belonging to a well‐characterized class of graphs, the tensor product of __G__~1~ and __G__~2~ admits a nowhere‐zero

Nowhere-zero 3-flows in products of grap

Nowhere-zero 3-flows in products of graphs

✍ Jinlong Shu; Cun-Quan Zhang 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

## Abstract A graph __G__ is an odd‐circuit tree if every block of __G__ is an odd length circuit. It is proved in this paper that the product of every pair of graphs __G__ and __H__ admits a nowhere‐zero 3‐flow unless __G__ is an odd‐circuit tree and __H__ has a bridge. This theorem is a partial r

Nowhere-zero flows in low genus graphs

✍ Martina Möller; Hans Georg Carstens; Gunnar Brinkmann 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 274 KB 👁 1 views