Flow-contractible configurations and group connectivity of signed graphs. (English) Zbl 1395.05075
Summary: F. Jaeger et al. [J. Comb. Theory, Ser. B 56, No. 2, 165–182 (1992; Zbl 0824.05043)] introduced the concept of group connectivity as a generalization of nowhere-zero flow for graphs. In this paper, we introduce group connectivity for signed graphs and establish some fundamental properties. For a finite abelian group \(A\), it is proved that an \(A\)-connected signed graph is a contractible configuration for \(A\)-flow problem of signed graphs. In addition, we give sufficient edge connectivity conditions for signed graphs to be \(A\)-connected and study the group connectivity of some families of signed graphs.
MSC:
| 05C22 | Signed and weighted graphs |
| 05C21 | Flows in graphs |
| 05C40 | Connectivity |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
Citations:
Zbl 0824.05043References:
| [1] | Catlin, P. A., The reduction of graph families under contraction, Discrete Math., 160, 67-80, (1996) · Zbl 0867.05081 |
| [2] | Cheng, J.; Lu, Y.; Luo, R.; Zhang, C.-Q., Signed graphs: from modulo flows to integer-valued flows, SIAM J. Discrete Math., 32, 2, 956-965, (2018) · Zbl 1385.05037 |
| [3] | Dirac, G. A., A property of 4-chromatic graphs and some remarks on critical graphs, J. Lond. Math. Soc., 27, 85-92, (1952) · Zbl 0046.41001 |
| [4] | R. Hušek, L. Mohelníková, R. Šámal, Group connectivity \(\mathbb{Z}_4 \mathbb{Z}_2^2\) arXiv:1711.0389; R. Hušek, L. Mohelníková, R. Šámal, Group connectivity \(\mathbb{Z}_4 \mathbb{Z}_2^2\) arXiv:1711.0389 |
| [5] | 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 |
| [6] | Kaiser, T.; Rollová, E., Nowhere-zero flows in signed series-parallel graphs, SIAM J. Discrete Math., 30, 2, 1248-1258, (2016) · Zbl 1338.05107 |
| [7] | Kochol, M., An equivalent version of the 3-flow conjecture, J. Combin. Theory Ser. B., 83, 258-261, (2001) · Zbl 1029.05088 |
| [8] | Lai, H.-J.; Li, X.; Shao, Y.; Zhan, M., Group connectivity and group colorings of graphs - A survey, Acta Math. Sin. English Ser., 27, 405-434, (2011) · Zbl 1233.05127 |
| [9] | Lai, H.-J.; Luo, R.; Zhang, C.-Q., Integer flow and orientation, (Beineke, L.; Wilson, R., Topics in Chromatic Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 156, (2015)), 181-198 · Zbl 1317.05004 |
| [10] | Lovász, L. M.; Thomassen, C.; Wu, Y.; Zhang, C.-Q., Nowhere-zero \(3\)-flows and modulo \(k\)-orientations, J. Combin. Theory Ser. B., 103, 587-598, (2013) · Zbl 1301.05154 |
| [11] | Luo, R.; Xu, R.; Yin, J.; Yu, G., Ore-condition and \(\mathbb{Z}_3\)-connectivity, European J. Combin., 29, 1587-1595, (2008) · Zbl 1171.05029 |
| [12] | Máčajová, E.; Rollová, E., Nowhere-zero flows on signed complete and complete bipartite graphs, J. Graph Theory, 78, 108-130, (2015) · Zbl 1307.05096 |
| [13] | Raspaud, A.; Zhu, X., Circular flow on signed graphs, J. Combin. Theory Ser. B., 101, 464-479, (2011) · Zbl 1408.05068 |
| [14] | Thomassen, C., The weak 3-flow conjecture and the weak circular flow conjecture, J. Combin. Theory Ser. B., 102, 521-529, (2012) · Zbl 1239.05083 |
| [15] | Tutte, W. T., On the embedding of linear graphs in surfaces, Proc. Lond. Math. Soc., 2, 51, 474-483, (1949) · Zbl 0033.30803 |
| [16] | Tutte, W. T., A contribution to the theory of chromatical polynomials, Canad. J. Math., 6, 80-91, (1954) · Zbl 0055.17101 |
| [17] | Wu, Y.; Ye, D.; Zang, W.; Zhang, C.-Q., Nowhere-zero 3-flow in signed graphs, SIAM J. Discrete Math., 28, 3, 1628-1637, (2014) · Zbl 1408.05069 |
| [18] | Xu, R.; Zhang, C.-Q., On flows in bidirected graphs, Discrete Math., 299, 335-343, (2005) · Zbl 1073.05033 |
| [19] | Zaslavsky, T., Signed graphs, Discrete Appl. Math., 4, 47-74, (1982) · Zbl 0476.05080 |
| [20] | Zaslavsky, T., Orientation of signed graphs, European J. Combin., 12, 361-375, (1991) · Zbl 0761.05095 |
| [21] | Zhang, C.-Q., Integer flows and cycle covers, (1997), Marcel Dekker |
| [22] | Zhu, X., Circular flow number of highly edge connected signed graphs, J. Combin. Theory Ser. B., 112, 93-103, (2015) · Zbl 1310.05112 |
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.
