Degree sum of a pair of independent edges and <i>Z</i><sub>3</sub>-connectivity

doi:10.1007/s11464-015-0457-z

Front. Math. China

2016, Vol. 11

Issue (6) : 1533-1567 https://doi.org/10.1007/s11464-015-0457-z

RESEARCH ARTICLE

Degree sum of a pair of independent edges and Z₃-connectivity

Ziwen HUANG,Xiangwen LI(

)

Department of Mathematics, Huazhong Normal University, Wuhan 430079, China

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

Abstract

Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E(G), define d(e) = d(u) + d(v). Let ℱ denote the set of all simple 2-edge-connected graphs on n≥4 vertices such that G ∈ ℱ if and only if d(e) + d(e')≥2n for every pair of independent edges e, e' of G. We prove in this paper that for each G ∈ ℱ, G is not Z₃-connected if and only if G is one of K₂,_n−2, K₃,_n−3, K⁺₂,_n−2, K⁺₃,_n−3 or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240].

Keywords Z₃-connectivity nowhere-zero 3-flow degree condition

Corresponding Author(s): Xiangwen LI

Issue Date: 18 October 2016

Cite this article:

Ziwen HUANG,Xiangwen LI. Degree sum of a pair of independent edges and Z₃-connectivity[J]. Front. Math. China, 2016, 11(6): 1533-1567.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-015-0457-z
https://academic.hep.com.cn/fmc/EN/Y2016/V11/I6/1533

1	Bondy J A, Murty U S R. Graph Theory with Application.New York: North-Holland, 1976 https://doi.org/10.1007/978-1-349-03521-2
2	Chen J, Eschen E, Lai H-J. Group connectivity of certain graphs. Ars Combin, 2008, 89: 141–158
3	DeVos M, Xu R,Yu G. Nowhere-zero Z3-flows through Z3-connectivity. Discrete Math, 2006, 306: 26–30 https://doi.org/10.1016/j.disc.2005.10.019
4	Fan G, Zhou C. Degree sum and nowhere-zero 3-flows. Discrete Math, 2008, 308: 6233–6240 https://doi.org/10.1016/j.disc.2007.11.045
5	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
6	Jaeger F, Linial N, Payan C, Tarsi M. 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
7	Lai H-J. Group connectivity of 3-edge-connected chordal graphs. Graphs Combin, 2000, 16: 165–176 https://doi.org/10.1007/s003730050014
8	Lai H-J. Nowhere-zero 3-flows in locally connected graphs. J Graph Theory, 2003, 4: 211–219 https://doi.org/10.1002/jgt.10085
9	Lai H-J, Li X, Shao Y, Zhan M. Group connectivity and group colorings of graphs—a survey. Acta Math Sin (Engl Ser), 2011, 27: 405–434 https://doi.org/10.1007/s10114-010-9746-3
10	Li X, Lai H-J, Shao Y. Degree condition and Z3-connectivity. Discrete Math, 2012, 312: 1658–1669 https://doi.org/10.1016/j.disc.2012.01.013
11	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
12	Luo R, Xu R, Yin J, Yu G. Ore-condition and Z3-connectivity. European J Combin, 2008, 29: 1587–1595 https://doi.org/10.1016/j.ejc.2007.11.014
13	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
14	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
15	Yang F, Li X. Degree sum of 3 independent vertices and Z3-connectivity. Discrete Math, 2013, 313: 2493–2505 https://doi.org/10.1016/j.disc.2013.07.009
16	Zhang X, Zhan M, Xu R, Shao Y, Li X, Lai H-J. Degree sum condition for Z3-connectivity in graphs. Discrete Math, 2010, 310: 3390–3397 https://doi.org/10.1016/j.disc.2010.08.004

[1]	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.
[2]	Yinghao ZHANG, Guizhen LIU. Nowhere-zero 3-flows in matroid base graph[J]. Front Math Chin, 2013, 8(1): 217-227.

Viewed

Full text

Abstract

Cited

Shared

Discussed