×

Group connectivity of graphs — a nonhomogeneous analogue of nowhere-zero flow properties. (English) Zbl 0824.05043

Summary: Let \(G= (V, E)\) be a digraph and \(f\) a mapping from \(E\) into an Abelian group \(A\). Associated with \(f\) is its boundary \(\partial f\), a mapping from \(V\) to \(A\), defined by \(\partial f(x)= \sum_{e\text{ leaving }x} f(e)- \sum_{e\text{ entering }x} f(e)\). We say that \(G\) is \(A\)- connected if for every \(b: V\to A\) with \(\sum_{x\in V} b(x)= 0\) there is an \(f: E\to A -\{0\}\) with \(b= \partial f\). This concept is closely related to the theory of nowhere-zero flows and is being studied here in the light of that theory.

MSC:

05C40 Connectivity
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
05B35 Combinatorial aspects of matroids and geometric lattices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon, N. Linial, and R. MeshulamJ. Combin. Theory Ser. A; N. Alon, N. Linial, and R. MeshulamJ. Combin. Theory Ser. A · Zbl 0739.11003
[2] Bollobas, B., (Extremal Graph Theory (1978), Academic Press: Academic Press San Francisco) · Zbl 0419.05031
[3] Bondy, J. A.; Murty, U. S.R, (Graph Theory with Applications (1976), North Holland: North Holland New York) · Zbl 1226.05083
[4] Edmonds, J., Minimum partition of a matroid into independent subsets, J. Res. Nat. Bur. Standards, 69B, 67-72 (1965) · Zbl 0192.09101
[5] Jaeger, F., Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B, 26, 205-216 (1979) · Zbl 0422.05028
[6] Jaeger, F., Nowhere-zero flow problems, (Beineke, L.; Wilson, R., Selected Topics in Graph Theory, Vol. 3 (1988), Academic Press: Academic Press London/New York), 91-95 · Zbl 0658.05034
[7] Jamshy, U.; Raspaud, A.; Tarsi, M., Short circuit covers for regular matroids with a nowhere zero 5-flow, J. Combin. Theory Ser. B, 43, 354-357 (1987) · Zbl 0659.05038
[8] Jamshy, U.; Tarsi, M., Cycle covering of binary matroids, J. Combin. Theory Ser. B, 46, 154-161 (1989)
[9] Nash-Williams, C. S.J. A., Edge-disjoint spanning trees of finite graphs, J. London Math. Soc., 36, 445-450 (1961) · Zbl 0102.38805
[10] Seymour, P. D., Nowhere-zero 6-flows, J. Combin. Theory Ser. B, 30, 130-135 (1981) · Zbl 0474.05028
[11] Tarsi, M., Nowhere zero flow and circuit covering in regular matroids, J. Combin. Theory Ser. B, 39, 346-352 (1985) · Zbl 0584.05018
[12] Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, 80-91 (1954) · Zbl 0055.17101
[13] Tutte, W. T., On the problem of decomposing a graph into \(n\) connected factors, J. Canad. Math. Soc., 36, 221-230 (1961) · Zbl 0096.38001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.