NZ‐flows in strong products of graphs |
| |
| Authors: | Wilfried Imrich Iztok Peterin Simon ?pacapan Cun‐Quan Zhang |
| |
| Institution: | 1. Montanuniversit?t Leoben, A‐8700 Leoben, Austria;2. University of Maribor, Feecs, Smetanova 17 2000 Maribor, Slovenia;3. University of Maribor, Fme, Smetanova 17 2000 Maribor, Slovenia;4. Department of Mathematics, West Virginia University, Morgantown, West Virginia 26506‐6310 |
| |
| 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 |
| |
| Keywords: | integer flows strong product paths and cycles |
|
|
