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

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

References

[1] Bondy J A, Murty U S R. Graph Theory with Application.New York: North-Holland, 1976

[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 Z₃-flows through Z₃-connectivity. Discrete Math, 2006, 306: 26–30

[4] Fan G, Zhou C. Degree sum and nowhere-zero 3-flows. Discrete Math, 2008, 308: 6233–6240

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

[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

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

[8] Lai H-J. Nowhere-zero 3-flows in locally connected graphs. J Graph Theory, 2003, 4: 211–219

[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

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

[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

[12] Luo R, Xu R, Yin J, Yu G. Ore-condition and Z₃-connectivity. European J Combin, 2008, 29: 1587–1595

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

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

[15] Yang F, Li X. Degree sum of 3 independent vertices and Z₃-connectivity. Discrete Math, 2013, 313: 2493–2505

[16] Zhang X, Zhan M, Xu R, Shao Y, Li X, Lai H-J. Degree sum condition for Z₃-connectivity in graphs. Discrete Math, 2010, 310: 3390–3397

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg