Premium
Nowhere‐zero 3‐flows in products of graphs
Author(s) -
Shu Jinlong,
Zhang CunQuan
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20095
Subject(s) - mathematics , combinatorics , cayley graph , bipartite graph , robertson–seymour theorem , discrete mathematics , conjecture , cubic graph , abelian group , graph , zero (linguistics) , chordal graph , line graph , 1 planar graph , voltage graph , linguistics , philosophy
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 result to the Tutte's 3‐flow conjecture and generalizes a result by Imrich and Skrekovski [7] that the product of two bipartite graphs admits a nowhere‐zero 3‐flow. A byproduct of this theorem is that every bridgeless Cayley graph G = Cay (Γ, S ) on an abelian group Γ with a minimal generating set S admits a nowhere‐zero 3‐flow except for odd prisms. © 2005 Wiley Periodicals, Inc. J Graph Theory