zbMATH — the first resource for mathematics

Every line graph of a 4-edge-connected graph is \(\mathbf Z_3\)-connected. (English) Zbl 1189.05086
Let \(G=(V,E)\) be a digraph and let \(A\) be a nontrivial additive abelian group with identity \(0\). Let \(f\) be a mapping from \(E\) into \(A\). Associated with \(f\) is its boundary \(\partial f\), a mapping from \(V\) to \(A\), defined by \(\partial f(x)=\sum_{e {\in E^{+}(x)}}f(e)-\sum_{e {\in E^{-}(x)}}f(e)\). An undirected graph \(G\) is \(A\)-connected if \(G\) has an orientation such that for every \(b\colon V\to A\) with \(\sum_{x\in V}b(x)=0\) there is an \(f\colon E\to A \setminus\{0\}\) with \(b=\partial f\). A function \(f\colon E\to A \diagdown \{0\}\) with \(\partial f = 0\) is called an \(A\)-NZF (nowhere zero flow). A function \(f\colon E\to Z \setminus \{0\}\), where \(Z\) is the group of integers, with \(\partial f = 0\) and such that for every \(e \in E\), \(0 < |f(e)| < k\) , is called a \(k\)-NZF. For a graph \(G\) let \(\Lambda (G)\) be the minimum \(k\) such that if \(A\) is an abelian group of order at least \(k\), then \(G\) is \(A\)-connected. W.T. Tutte [“A contribution to the theory of chromatic polynomials”, Canadian J. Math. 6, 80–91 (1954; Zbl 0055.17101)] conjectured that every 4-edge connected graph has a 3-NZF. Z.-H. Chen, H.-J. Lai, and H. Lai [“Nowhere zero flows in line graphs”, Discrete Math. 230, No. 1-3, 133–141 (2001; Zbl 0982.05080)] proved that if every 4-edge connected line graph has a 3-NZF, then every 4-edge connected graph has a 3-NZF. For a connected graph \(G\), a partition \((E_{1}, E_{2}, \dots , E_{n})\) of the edges of \(G\) is a \((\geq 4)\)-clique partition provided \(G(E_{i})\) is spanned by a complete graph with 4 or more vertices for \(i = 1,2, \dots, n\).
The main result of this paper is if \(G\) is 4-edge connected and \(G\) has a \((\geq 4)\)-clique partition, then \(\Lambda (G) \leq 3\). As a consequence every line graph of a 4-edge connected graph has a 3-NZF.

05C40 Connectivity
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), American Elsevier New York · Zbl 1134.05001
[2] Chen, Z.-H.; Lai, H.-J.; Lai, H.Y., Nowhere zero flows in line graphs, Discrete math., 230, 133-141, (2001) · Zbl 0982.05080
[3] Jaeger, F., Nowhere-zero flow problems, (), 91-95
[4] 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
[5] Kochol, M., An equivalent version of the 3-flow conjecture, J. combin. theory ser. B, 83, 258-261, (2001) · Zbl 1029.05088
[6] Lai, H.-J., Group connectivity of 3-edge-connected chordal graphs, Graphs combin., 16, 165-176, (2000) · Zbl 0966.05041
[7] Lai, H.-J., Nowhere-zero 3-flows in locally connected graphs, J. graph theory, 42, 211-219, (2003) · Zbl 1015.05037
[8] Tutte, W.T., A contribution to the theory of chromatical polynomials, Canad. J. math., 6, 80-91, (1954) · Zbl 0055.17101
[9] 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.