Nowhere-zero 3-flows in Cayley graphs and Sylow 2-subgroups
Mária Nánásiová
and Martin Škoviera
DOI: 10.1007/s10801-008-0153-0
Abstract
Tutte's 3-Flow Conjecture suggests that every bridgeless graph with no 3-edge-cut can have its edges directed and labelled by the numbers 1 or 2 in such a way that at each vertex the sum of incoming values equals the sum of outgoing values. In this paper we show that Tutte's 3-Flow Conjecture is true for Cayley graphs of groups whose Sylow 2-subgroup is a direct factor of the group; in particular, it is true for Cayley graphs of nilpotent groups. This improves a recent result of Potočnik et al. (Discrete Math. 297:119-127, 2005) concerning nowhere-zero 3-flows in abelian Cayley graphs.
Pages: 103–111
Keywords: keywords nowhere-zero flow; Cayley graph; group centre; Sylow subgroup; nilpotent group
Full Text: PDF
References
1. Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Elsevier, New York (1976)
2. DeVos, M., Xu, R., Yu, G.: Nowhere-zero Z3-flows through Z3-connectivity. Discrete Math. 306, 26-30 (2006)
3. Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)
4. Gross, J.L., Tucker, T.W.: Topological Graph Theory. Wiley, New York (1987)
5. Grötzsch, H.: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Zeitschrift d. M.-L.- Universität Halle-Wittenberg. Math.-Naturwiss. Reihe 8, 109-120 (1958/1959)
6. Imrich, W., Škrekovski, R.: A theorem on integer flows on Cartesian products of graphs. J. Graph. Theory 43, 93-98 (2003)
7. Jaeger, F.: Nowhere-zero flow problems. In: Beineke, L.W., Wilson, R.J. (eds.) Selected Topics in Graph Theory, vol. 3, pp. 71-95. Academic Press, London (1988)
8. Kochol, M.: An equivalent form of the 3-flow conjecture. J. Combin. Theory Ser. B 83, 258-261 (2001)
9. Kochol, M.: Equivalence between Hamiltonicity and flow conjectures, and the sublinear defect property. Discrete Math. 254, 221-230 (2002)
10. Lai, H.-J.: Nowhere-zero 3-flows in locally connected graphs. J. Graph Theory 42, 211-219 (2003)
11. Poto\check cnik, P., Škoviera, M., Škrekovski, R.: Nowhere-zero 3-flows in Abelian Cayley Graphs. Discrete
2. DeVos, M., Xu, R., Yu, G.: Nowhere-zero Z3-flows through Z3-connectivity. Discrete Math. 306, 26-30 (2006)
3. Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)
4. Gross, J.L., Tucker, T.W.: Topological Graph Theory. Wiley, New York (1987)
5. Grötzsch, H.: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Zeitschrift d. M.-L.- Universität Halle-Wittenberg. Math.-Naturwiss. Reihe 8, 109-120 (1958/1959)
6. Imrich, W., Škrekovski, R.: A theorem on integer flows on Cartesian products of graphs. J. Graph. Theory 43, 93-98 (2003)
7. Jaeger, F.: Nowhere-zero flow problems. In: Beineke, L.W., Wilson, R.J. (eds.) Selected Topics in Graph Theory, vol. 3, pp. 71-95. Academic Press, London (1988)
8. Kochol, M.: An equivalent form of the 3-flow conjecture. J. Combin. Theory Ser. B 83, 258-261 (2001)
9. Kochol, M.: Equivalence between Hamiltonicity and flow conjectures, and the sublinear defect property. Discrete Math. 254, 221-230 (2002)
10. Lai, H.-J.: Nowhere-zero 3-flows in locally connected graphs. J. Graph Theory 42, 211-219 (2003)
11. Poto\check cnik, P., Škoviera, M., Škrekovski, R.: Nowhere-zero 3-flows in Abelian Cayley Graphs. Discrete