We introduce a model of information dissemination in signed networks. It is a discrete-time process in which uninformed actors incrementally receive information from their informed neighbors or from the outside. Our goal is to minimize the number of confused actors — that is, the number of actors who receive contradictory information. We prove upper bounds for the number of confused actors in signed networks and in equivalence classes of signed networks. In particular, we show that there are signed networks where, for any information placement strategy, almost 60% of the actors are confused. Furthermore, this is also the case when considering the minimum number of confused actors within an equivalence class of signed graphs.

Abstract. Thomassen [ J. Combin. Theory Ser. B, 141 (2020), pp. 343–351] asked whether every [Formula: see text]-edge-connected [Formula: see text]-regular graph of even order has [Formula: see text] pairwise disjoint perfect matchings. We show that this is not the case if [Formula: see text]. Together with a recent result of Mattiolo and Steffen [ J. Graph Theory, 99 (2022), pp. 107–116] this solves Thomassen’s problem for all even [Formula: see text]. It turns out that our methods are limited to the even case of Thomassen’s problem. We then prove some equivalences of statements on pairwise disjoint perfect matchings in highly edge-connected regular graphs, where the perfect matchings contain or avoid fixed sets of edges. Based on these results we relate statements on pairwise disjoint perfect matchings of 5-edge-connected 5-regular graphs to well-known conjectures for cubic graphs, such as the Fan–Raspaud conjecture, the Berge–Fulkerson conjecture, and the 5-cycle double cover conjecture.

Many basic properties in Tutte's flow theory for unsigned graphs do not have their counterparts for signed graphs. However, signed graphs without long barbells in many ways behave like unsigned graphs from the point view of flows. In this paper, we study whether some basic properties in Tutte's flow theory remain valid for this family of signed graphs. Specifically let $(G,\sigma)$ be a flow-admissible signed graph without long barbells. We show that it admits a nowhere-zero 6-flow and that it admits a nowhere-zero modulo $k$-flow if and only if it admits a nowhere-zero integer $k$-flow for each integer $k\geq 3$ and $k \not = 4$. We also show that each nowhere-zero positive integer $k$-flow of $(G,\sigma)$ can be expressed as the sum of some 2-flows. For general graphs, we show that every nowhere-zero $\frac{p}{q}$-flow can be normalized in such a way, that each flow value is a multiple of $\frac{1}{2q}$. As a consequence we prove the equality of the integer flow number and the ceiling of the circular flow number for flow-admissible signed graphs without long barbells.