# zbMATH — the first resource for mathematics

Degree sum condition for $$Z_{3}$$-connectivity in graphs. (English) Zbl 1210.05028
Summary: Let $$G$$ be a 2-edge-connected simple graph on $$n$$ vertices, let $$A$$ denote an Abelian group with the identity element $$0$$, and let $$D$$ be an orientation of $$G$$. The boundary of a function $$f: E(G)\to A$$ is the function $$\partial f: V(G)\to A$$ given by $\partial f(v)= \sum_{e\in E^+(v)} f(e)- \sum_{e\in E^-(v)} f(e),$ where $$E^+(v)$$ is the set of edges with tail $$v$$ and $$E^-(v)$$ is the set of edges with head $$v$$. A graph $$G$$ is $$A$$-connected if for every $$b: V(G)\to A$$ with $$\sum_{v\in V(G)} b(v)= 0$$, there is a function $$f: E(G)\to A-\{0\}$$ such that $$\partial f= b$$.
In this paper, we prove that if $$d(x)+ d(y)\geq n$$ for each $$xy\in E(G)$$, then $$G$$ is not $$Z_3$$-connected if and only if $$G$$ is either one of 15 specific graphs or one of $$K_{2,n-2}$$, $$K_{3,n-3}$$, $$K^+_{2,n-2}$$ or $$K^+_{3,n-3}$$ for $$n\geq 6$$, where $$K^+_{r,s}$$ denotes the graph obtained from $$K_{r,s}$$ by adding an edge joining two vertices of maximum degree. This result generalizes the result in [Discrete Math. 308, No. 24, 6233–6240 (2008; Zbl 1167.05309)] by G. Fan and C. Zhou.

##### MSC:
 05C07 Vertex degrees 05C40 Connectivity
##### Keywords:
$$Z_{3}$$-connectivity; nowhere-zero 3-flow; degree sum
Full Text:
##### References:
  Bondy, J.A.; Murty, U.S.R., Graph theory with application, (1976), North-Holland New York · Zbl 1134.05001  Chen, J.J.; Eschen, E.; Lai, H.J., Group connectivity of certain graphs, Ars combin., 89, 141-158, (2008) · Zbl 1224.05267  DeVos, M.; Xu, R.; Yu, G., Nowhere-zero $$Z_3$$-flows through $$Z_3$$-connectivity, Discrete math., 306, 26-30, (2006) · Zbl 1086.05043  Fan, G.; Lai, H.J.; Xu, R.; Zhang, C.Q.; Zhou, C., Nowhere-zero 3-flows in triangularly connected graphs, J. combin. theory ser. B, 98, 1325-1336, (2008) · Zbl 1171.05026  Fan, G.; Zhou, C., Degree sum and nowhere-zero 3-flows, Discrete math., 308, 6233-6240, (2008) · Zbl 1167.05309  Fan, G.; Zhou, C., Ore condition and nowhere-zero 3-flows, SIAM J. discrete math., 22, 288-294, (2008) · Zbl 1170.05025  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, 56, 165-182, (1992) · Zbl 0824.05043  Kochol, M., An equivalent version of the 3-flow conjecture, J. combin. theory, ser. B, 83, 258-261, (2001) · Zbl 1029.05088  Lai, H.J., Group connectivity of 3-edge-connected chordal graphs, Graphs and combin., 16, 165-176, (2000) · Zbl 0966.05041  Luo, R.; Xu, R.; Yin, J.H.; Yu, G.X., Ore-condition and $$Z_3$$-connectivity, European J. combin., 29, 1587-1595, (2008) · Zbl 1171.05029  Tutte, W.T., A contribution on the theory of chromatic polynomial, Canad. J. math., 6, 80-91, (1954) · Zbl 0055.17101  Tutte, W.T., On the algebraic theory of graph colorings, J. combin. theory, 1, 15-50, (1966) · Zbl 0139.41402  Zhang, C.Q., Integer flows and cycle covers of graphs, (1997), Marcel Dekker New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.