Frontiers of Mathematics in China >
Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group
Received date: 07 Aug 2013
Accepted date: 14 Apr 2014
Published date: 12 Feb 2015
Copyright
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].
Liangchen LI , Xiangwen LI . Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group[J]. Frontiers of Mathematics in China, 2015 , 10(2) : 293 -302 . DOI: 10.1007/s11464-014-0378-2
| 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 Z3-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
|
/
| 〈 |
|
〉 |