×

Nowhere-zero 3-flows in products of graphs. (English) Zbl 1069.05040

Summary: 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 W. Imrich and R. Skrekovski [J. Graph Theory 43, 93–98 (2003; Zbl 1019.05058)] 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 = \text{Cay}(\Gamma ,S)\) on an abelian group \(\Gamma\) with a minimal generating set \(S\) admits a nowhere-zero 3-flow except for odd prisms.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C75 Structural characterization of families of graphs

Citations:

Zbl 1019.05058
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, SIAM J Discrete Math 9 pp 151– (1996)
[2] and , Graph theory with applications, Macmillan, London, 1976. · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[3] Catlin, J Graph Theory 13 pp 465– (1989)
[4] Fleischner, Monatsh Math 81 pp 267– (1976)
[5] , Eulerian Graphs and Related Topics, Part 1, Vol. 1, Ann Discrete Math, Vol. 45, North-Holland, 1990.
[6] and , P(D)-compatible Eulerian trails in digraphs and a new splitting lemma, in Contemporary Methods in Graph Theory, , (Editor), B. I. Wissenschaftverlag, 1990, pp. 291-303. · Zbl 0752.05038
[7] Imrich, J Graph Theory 43 pp 93– (2003)
[8] Jaeger, J Combin Theory Ser B 26 pp 205– (1979)
[9] Kochol, J Combin Theory Ser B 83 pp 258– (2001)
[10] Kochol, Discrete Math 254 pp 221– (2002)
[11] Seymour, J Combin Theory Ser B 30 pp 130– (1981)
[12] , Grötzsch’s Theorem dualized, M. Math Thesis, University of Waterloo, Ontario, Canada, 1976.
[13] Steinberg, Ars Combin 28 pp 15– (1989)
[14] Tutte, Proc Lond Math Soc Ser 2 51 pp 474– (1949)
[15] Tutte, Canad J Math 6 pp 80– (1954) · Zbl 0055.17101 · doi:10.4153/CJM-1954-010-9
[16] Tutte, Canad J Math 8 pp 13– (1956) · Zbl 0070.02302 · doi:10.4153/CJM-1956-004-9
[17] Zhang, J Graph Theory 40 pp 147– (2002)
[18] , Integer Flows and Cycle Covers of Graphs, Marcel Dekker, New York, 1997.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.