The Effect of Local Majority on Global Majorityin Connected Graphs
Tóm tắt
Let
$$\mathcal G$$
be an infinite family of connected graphs and let k be a positive integer. We say that k is 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 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 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.
Tài liệu tham khảo
Auletta, V., Caragiannis, I., Ferraioli, D., Galdi, C., Persiano, G.: Minority becomes majority in social networks. In: Markakis, E., Schäfer, G. (eds.) Web and Internet Economics. Lecture Notes in Computer Science, vol. 9470. Springer, Berlin (2015)
Berger, E.: Dynamic monopolies of constant size. J. Comb. Theory Ser. B 83(2), 191–200 (2001)
Broere, I., Hattingh, J., Henning, M.A., McRae, A.: Majority domination in graphs. Discrete Mathematics 138(1), 125–135 (1995)
Caro, Y., Hansberg, A., Montejano, A.: Zero-sum subsequences in bounded-sum \(\{-1,1\}\)-sequences (2016). arXiv:1612.06523
Curtis, E., Ingerman, D., Morrow, J.: Circular planar graphs and resistor networks. Linear Algebra Appl. 283(1–3), 115–150 (1998)
Erdős, P.: Graph theory and probability. Can. J. Math. 11, 34–38 (1959)
Fishburn, P., Hwang, F., Lee, H.: Do local majorities force a global majority? Discrete Math. 61(2), 165–179 (1986)
Füredi, Z., Mubayi, D.: Signed domination in regular graphs and set-systems. J. Comb. Theory Ser. B 76(2), 223–239 (1999)
Peleg, D.: Local majorities, coalitions and monopolies in graphs: a review. Theor. Comput. Sci. 282(2), 231–257 (2002)
Poghosyan, A., Zverovich, V.: Discrepancy and signed domination in graphs and hypergraphs. Discrete Math. 310(15), 2091–2099 (2010)
Truemper, K.: On the delta-wye reduction for planar graphs. J. Graph Theory 13(2), 141–148 (1989)
Woodall, D.: Local and global proportionality. Discrete Math. 102(3), 315–328 (1992)
Xu, B.: On signed edge domination numbers of graphs. Discrete Math. 239(1–3), 179–189 (2001)