Premium
NZ‐flows in strong products of graphs
Author(s) -
Imrich Wilfried,
Peterin Iztok,
Špacapan Simon,
Zhang CunQuan
Publication year - 2010
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.20455
Subject(s) - mathematics , combinatorics , constructive , contractible space , tree (set theory) , constructive proof , product (mathematics) , graph , flow (mathematics) , discrete mathematics , computer science , geometry , process (computing) , operating system
We prove that the strong product G 1 ⊠ G 2 of G 1 and G 2 is ℤ 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. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 267–276, 2010