NZ‐flows in strong products of graphs
Wilfried Imrich, Iztok Peterin, Simon Špacapan, Cun‐Quan Zhang · Journal of Graph Theory · 2009
Abstract We prove that the strong product G1⊠ G2 of G1 and G2 is ℤ3‐flow contractible if and only if G1⊠ G2 is not T⊠ K2, where T is a tree (we call T⊠ K2 a K4‐tree). It follows that G1⊠ G2 admits an NZ 3 ‐flow unless G1⊠ G2 is a K4 ‐tree. We also give a constructive proof that yields a polynomial algorithm whose output is an NZ 3‐flow if G1⊠ G2 is not a K4 ‐tree, and an NZ 4‐flow otherwise. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 267–276, 2010