Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group

Abstract

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper, we show that this conjecture is true for Cayley graph on generalized dihedral groups and generalized quaternion groups, which generalizes the result of F. Yang and X. Li [Inform. Process. Lett., 2011, 111: 416–419]. We also generalizes an early result of M. Nánásiová and M. Škoviera [J. Algebraic Combin., 2009, 30: 103–110].

Keywords

Nowhere-zero 3-flow / Cayley graph / generalized dihedral group / generalized quaternion group

References

[1] Alspach B, Liu Y, Zhang C-Q. Nowhere-zero 4-flows and Cayley graphs on solvable groups. SIAM J Discrete Math, 1996, 9: 151-154

[2] Bondy J A, Murty U S R. Graphs Theory with Applications. New York: Macmillan Press, 1976

[3] Fan G, Zhou C. Ore condition and nowhere-zero 3-flows. SIAM J Discrete Math, 2008, 22: 288-294

[4] Jaeger F. Flows and generalized coloring theorems in graphs. J Combin Theory Ser B, 1979, 26: 205-216

[5] Jaeger J, Linial N, Payan C, Tarsi N. Group connectivity of graphs—a nonhomogeneous analogue of nowhere zero flow properties. J Combin Theory Ser B, 1992, 56: 165-182

[6] Lai H-J. Group connectivity of 3-edge-connected chordal graphs. Graphs Combin, 2000, 16: 165-176

[7] Li L, Li X, Shu C. Group connectivity of bridged graphs. Graphs Combin, 2013, 29: 1059-1066

[8] Li X, Shao Y, Lai H-J. Degree condition and Z₃-connectivity. Discrete Math, 2012, 312: 1658-1669

[9] Lovász L M, Thomassen C, Wu Y, Zhang C-Q. Nowhere-zero 3-flows and modulo k-orientations. J Combin Theory Ser B, 2013, 103: 587-598

[10] Nánásiová M, Škoviera M. Nowhere-zero flows in Cayley graphs and Sylow 2-subgroups. J Algebraic Combin, 2009, 30: 103-110

[11] Nedela R, Škoviera M. Cayley snarks and almost simple groups. Combinatorica, 2001, 21: 583-590

[12] Potočnik P. Edge-colorings of cubic graphs admitting a solvable ‘vertex-transitive group’. J Combin Theory Ser B, 2004, 91: 289-300

[13] Potočnik P, Škoviera M, Škrekovski R. Nowhere-zero 3-flows in abelian Cayley raphs. Discrete Math, 2005, 297: 119-127

[14] Thomassen C. The weak 3-flow conjecture and the weak circular flow conjecture. J Combin Theory Ser B, 2012, 102: 521-529

[15] Tutte W T. On the imbedding of linear graphs in surfaces. Proc Lond Math Soc, Ser 2, 1949, 51: 474-483

[16] Tutte W T. A contribution on the theory of chromatic polynomial. Canad J Math, 1954, 6: 80-91

[17] Tutte W T. On the algebraic theory of graph colorings. J Combin Theory, 1966, 1: 15-50

[18] Watkins A. E. Connectivity of transitive graphs. J Combin Theory, 1970, 8: 23-29

[19] Yang F, Li X. Nowhere-zero 3-flows in dihedral Cayley graphs. Inform Process Lett, 2011, 111: 416-419

[20] Yin J, Zhang Y. Pósa-condition and nowhere-zero 3-flows. Discrete Math, 2010, 311: 897-907

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg