Degree sum of a pair of independent edges and Z3-connectivity

doi:10.1007/s11464-015-0457-z

Frontiers of Mathematics in China

2016, Vol. 11

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

本期目录

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

Ziwen HUANG,Xiangwen LI(

)

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

全文: PDF(339 KB)

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].

Key words： Z₃-connectivity nowhere-zero 3-flow degree condition

收稿日期: 2014-09-12 出版日期: 2016-10-18

Corresponding Author(s): Xiangwen LI

引用本文:

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

链接本文:

https://academic.hep.com.cn/fmc/CN/10.1007/s11464-015-0457-z
https://academic.hep.com.cn/fmc/CN/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

Viewed

Full text

Abstract

Cited

Shared

Discussed