The effect of local majority on global majority in connected graphs
read the original abstract
Let ${\mathcal G}$ be an infinite family of connected graphs and let $k$ be a positive integer. We say that $k$ is ${\it forcing}$ for ${\mathcal G}$ if for all $G \in {\mathcal G}$ but finitely many, the following holds. Any $\{-1,1\}$-weighing of the edges of $G$ for which all connected subgraphs on $k$ edges are positively weighted implies that $G$ is positively weighted. Otherwise, we say that it is ${\it weakly~forcing}$ for ${\mathcal G}$ if any such weighing implies that the weight of $G$ is bounded from below by a constant. Otherwise we say that $k$ ${\it collapses}$ for ${\mathcal G}$. We classify $k$ for some of the most prominent classes of graphs, such as all connected graphs, all connected graphs with a given maximum degree and all connected graphs with a given average degree.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.