𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Superposition and Constructions of Graphs Without Nowhere-zero k-flows

✍ Scribed by Martin Kochol

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
492 KB
Volume
23
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

Using multi-terminal networks we build methods on constructing graphs without nowhere-zero group-and integer-valued flows. In this way we unify known constructions of snarks (nontrivial cubic graphs without edge-3-colorings, or equivalently, without nowhere-zero 4-flows) and provide new ones in the same process. Our methods also imply new complexity results about nowhere-zero flows in graphs and state equivalences of Tutte's 3-and 5-flow conjectures with formally weaker statements.

📜 SIMILAR VOLUMES

The size of graphs without nowhere-zero
The size of graphs without nowhere-zero 4-flows
✍ Hong-Jian Lai 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 428 KB 👁 1 views

Let G be a 2-edge-connected simple graph with order n. We show that if IV(G)l 5 17, then either G has a nowhere-zero 4-flow, or G is contractible to the Petersen graph. We also show that for n large, if I€(G)J L (' 2 17) + 34, then either G has a nonwhere-zero 4-flow, or G can be contracted to the P

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