𝔖 Bobbio Scriptorium
✦   LIBER   ✦

NZ-flows in strong products of graphs

✍ Scribed by Wilfried Imrich; Iztok Peterin; Simon Špacapan; Cun-Quan Zhang

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
116 KB
Volume
64
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 algorithm whose output is an NZ 3-flow if G 1 G 2 is not a K 4 -tree, and an NZ 4-flow otherwise.

📜 SIMILAR VOLUMES

Hamilton cycles in strong products of gr
Hamilton cycles in strong products of graphs
✍ Daniel Král'; Jana Maxová; Robert Šámal; Pavel Podbrdský 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 229 KB

## Abstract We prove that the strong product of any __n__ connected graphs of maximum degree at most __n__ contains a Hamilton cycle. In particular, __G__^Δ(__G__)^ is hamiltonian for each connected graph __G__, which answers in affirmative a conjecture of Bermond, Germa, and Heydemann. © 2005 Wile

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

Hamiltonian threshold for strong product
Hamiltonian threshold for strong products of graphs
✍ Daniel Král'; Ladislav Stacho 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB

## Abstract We prove that the strong product of any at least ${({\rm ln}}\, {2})\Delta+{O}(\sqrt{\Delta})$ non‐trivial connected graphs of maximum degree at most Δ is pancyclic. The obtained result is asymptotically best possible since the strong product of ⌊(ln 2)__D__⌋ stars __K__~1,__D__~ is not

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

A theorem on integer flows on cartesian
A theorem on integer flows on cartesian products of graphs
✍ Wilfried Imrich; Riste Škrekovski 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB

## Abstract It is shown that the Cartesian product of two nontrivial connected graphs admits a nowhere‐zero 4‐flow. If both factors are bipartite, then the product admits a nowhere‐zero 3‐flow. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 93–98, 2003

The Algebra of Flows in Graphs
The Algebra of Flows in Graphs
✍ David G Wagner 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 452 KB

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-valu