NZ‐flows in strong products of graphs
Copyright policy )NZ‐flows in strong products of graphs
AbstractWe 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
- University of Maribor Slovenia
- West Virginia University United States
- University of Leoben Austria
paths, mathematics, graph theory, Graph operations (line graphs, products, etc.), integer flows, cycles, cikli, strong product, info:eu-repo/classification/udc/519.17, teorija grafov, matematika, krepki produkt, nikjer ničelni pretok, paths and cycles, poti, Flows in graphs, celoštevilski pretoki
paths, mathematics, graph theory, Graph operations (line graphs, products, etc.), integer flows, cycles, cikli, strong product, info:eu-repo/classification/udc/519.17, teorija grafov, matematika, krepki produkt, nikjer ničelni pretok, paths and cycles, poti, Flows in graphs, celoštevilski pretoki
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).6 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!