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.

05C07 Vertex degrees
05C40 Connectivity
Full Text: DOI
[1] Bondy, J.A.; Murty, U.S.R., Graph theory with application, (1976), North-Holland New York · Zbl 1134.05001
[2] Chen, J.J.; Eschen, E.; Lai, H.J., Group connectivity of certain graphs, Ars combin., 89, 141-158, (2008) · Zbl 1224.05267
[3] DeVos, M.; Xu, R.; Yu, G., Nowhere-zero \(Z_3\)-flows through \(Z_3\)-connectivity, Discrete math., 306, 26-30, (2006) · Zbl 1086.05043
[4] 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
[5] Fan, G.; Zhou, C., Degree sum and nowhere-zero 3-flows, Discrete math., 308, 6233-6240, (2008) · Zbl 1167.05309
[6] Fan, G.; Zhou, C., Ore condition and nowhere-zero 3-flows, SIAM J. discrete math., 22, 288-294, (2008) · Zbl 1170.05025
[7] 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
[8] Kochol, M., An equivalent version of the 3-flow conjecture, J. combin. theory, ser. B, 83, 258-261, (2001) · Zbl 1029.05088
[9] Lai, H.J., Group connectivity of 3-edge-connected chordal graphs, Graphs and combin., 16, 165-176, (2000) · Zbl 0966.05041
[10] 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
[11] Tutte, W.T., A contribution on the theory of chromatic polynomial, Canad. J. math., 6, 80-91, (1954) · Zbl 0055.17101
[12] Tutte, W.T., On the algebraic theory of graph colorings, J. combin. theory, 1, 15-50, (1966) · Zbl 0139.41402
[13] 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.