Search

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.

This paper proves that every planar graph without cycles of length 4, 7, or 9 is DP-3-colorable., Comment: 12 pages, 2 figures

A graph $G$ is $(I,F)$-partitionable if its vertex set can be partitioned into two parts such that one part is an independent set, and the other induces a forest. In this paper, we prove that every planar graph without cycles of length $4, 6, 9$ is $(I,F)$-partitionable., Comment: 9 pages, 5 figures

The study on parity signed graphs was initiated by Acharya and Kureethara very recently and then followed by Zaslavsky etc.. Let $(G,\sigma)$ be a signed graph on $n$ vertices. If $(G,\sigma)$ is switch-equivalent to $(G,+)$ at a set of $\lfloor \frac{n}{2} \rfloor$ many vertices, then we call $(G,\sigma)$ a parity signed graph and $\sigma$ a parity-signature. $\Sigma^{-}(G)$ is defined as the set of the number of negative edges of $(G,\sigma)$ over all possible parity-signatures $\sigma$. The $rna$ number $\sigma^-(G)$ of $G$ is given by $\sigma^-(G)=\min \Sigma^{-}(G)$. In other words, $\sigma^-(G)$ is the smallest cut size that has nearly equal sides. In this paper, all graphs considered are finite, simple and connected. We apply switch method to the characterization of parity signed graphs and the study on the $rna$ number. We prove that: for any graph $G$, $\Sigma^{-}(G)=\left\{\sigma^{-}(G)\right\}$ if and only if $G$ is $K_{1, n-1} $ with $n$ even or $K_{n}$. This confirms a conjecture proposed in [M. Acharya and J.V. Kureethara. Parity labeling in signed graphs. J. Prime Res. Math., to appear. arXiv:2012.07737]. Moreover, we prove a nontrivial upper bound for the $rna$ number: for any graph $G$ on $m$ edges and $n$ ($n\geq 4$) vertices, $\sigma^{-}(G)\leq \lfloor \frac{m}{2}+\frac{n}{4} \rfloor$. We show that $K_n$, $K_n-e$ and $K_n-\triangle$ are the only three graphs reaching this bound. This is the first upper bound for the $rna$ number so far. Finally, we prove that: for any graph $G$, $\sigma^-(G)+\sigma^-(\overline{G})\leq \sigma^-(G\cup \overline{G})$, where $\overline{G}$ is the complement of $G$. This solves a problem proposed in [M. Acharya, J.V. Kureethara and T. Zaslavsky. Characterizations of some parity signed graphs. 2020, arXiv:2006.03584v3]., Comment: 10 pages