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

doi:10.1007/s11464-014-0378-2

Front. Math. China

2015, Vol. 10

Issue (2) : 293-302 https://doi.org/10.1007/s11464-014-0378-2

RESEARCH ARTICLE

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

Liangchen LI^1,²,Xiangwen LI^1,^*(

)

1. Department of Mathematics, Huazhong Normal University, Wuhan 430079, China
2. Department of Mathematics, Luoyang Normal University, Luoyang 471022, China

Download: PDF(126 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Xiangwen LI

Issue Date: 12 February 2015

Cite this article:

Liangchen LI,Xiangwen LI. Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group[J]. Front. Math. China, 2015, 10(2): 293-302.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-014-0378-2
https://academic.hep.com.cn/fmc/EN/Y2015/V10/I2/293

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 https://doi.org/10.1137/S0895480193258017
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 https://doi.org/10.1137/060677744
4	Jaeger F. Flows and generalized coloring theorems in graphs. J Combin Theory Ser B, 1979, 26: 205-216 https://doi.org/10.1016/0095-8956(79)90057-1
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 https://doi.org/10.1016/0095-8956(92)90016-Q
6	Lai H-J. Group connectivity of 3-edge-connected chordal graphs. Graphs Combin, 2000, 16: 165-176 https://doi.org/10.1007/s003730050014
7	Li L, Li X, Shu C. Group connectivity of bridged graphs. Graphs Combin, 2013, 29: 1059-1066 https://doi.org/10.1007/s00373-012-1154-2
8	Li X, Shao Y, Lai H-J. Degree condition and Z3-connectivity. Discrete Math, 2012, 312: 1658-1669 https://doi.org/10.1016/j.disc.2012.01.013
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 https://doi.org/10.1016/j.jctb.2013.06.003
10	Nánásiová M, ?koviera M. Nowhere-zero flows in Cayley graphs and Sylow 2-subgroups. J Algebraic Combin, 2009, 30: 103-110 https://doi.org/10.1007/s10801-008-0153-0
11	Nedela R, ?koviera M. Cayley snarks and almost simple groups. Combinatorica, 2001, 21: 583-590 https://doi.org/10.1007/s004930100014
12	Poto?nik P. Edge-colorings of cubic graphs admitting a solvable ‘vertex-transitive group’. J Combin Theory Ser B, 2004, 91: 289-300 https://doi.org/10.1016/j.jctb.2004.01.003
13	Poto?nik P, ?koviera M, ?krekovski R. Nowhere-zero 3-flows in abelian Cayley raphs. Discrete Math, 2005, 297: 119-127 https://doi.org/10.1016/j.disc.2005.04.013
14	Thomassen C. The weak 3-flow conjecture and the weak circular flow conjecture. J Combin Theory Ser B, 2012, 102: 521-529 https://doi.org/10.1016/j.jctb.2011.09.003
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 https://doi.org/10.4153/CJM-1954-010-9
17	Tutte W T. On the algebraic theory of graph colorings. J Combin Theory, 1966, 1: 15-50 https://doi.org/10.1016/S0021-9800(66)80004-2
18	Watkins A. E. Connectivity of transitive graphs. J Combin Theory, 1970, 8: 23-29 https://doi.org/10.1016/S0021-9800(70)80005-9
19	Yang F, Li X. Nowhere-zero 3-flows in dihedral Cayley graphs. Inform Process Lett, 2011, 111: 416-419 https://doi.org/10.1016/j.ipl.2011.01.017
20	Yin J, Zhang Y. Pósa-condition and nowhere-zero 3-flows. Discrete Math, 2010, 311: 897-907 https://doi.org/10.1016/j.disc.2011.02.023

[1]	Ziwen HUANG,Xiangwen LI. Degree sum of a pair of independent edges and Z₃-connectivity[J]. Front. Math. China, 2016, 11(6): 1533-1567.
[2]	Yinghao ZHANG, Guizhen LIU. Nowhere-zero 3-flows in matroid base graph[J]. Front Math Chin, 2013, 8(1): 217-227.
[3]	PENG Xing, WANG Dianjun. Cayley digraphs and lexicographic product[J]. Front. Math. China, 2007, 2(3): 447-454.

Viewed

Full text

Abstract

Cited

Shared

Discussed