Azarbaijan Shahid Madani University Communications in Combinatorics and Optimization 2538-2128 11 4 2026 12 01 Majority Sets in Graphs 1107 1123 15062 10.22049/cco.2025.30739.2602 EN Mustapha Chellali AMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria Stephen T. Hedetniemi Professor and Chair Emeritus of Computer Science, Clemson University, Clemson, SC 29634 USA Nacéra Meddah AMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria Journal Article 2025 06 26 A set of vertices $S\subseteq V$ in a graph $G=(V,E)$ is called an internal majority set if for every vertex $v\in S$, a majority of the neighbors of $v$ are in $S$, or equivalently, every vertex $v\in S$ has fewer neighbors in $V-S=\overline{S}$ than it has in $S$. A set $S$ is called an external majority set if for every vertex $v\in\overline{S}$, a majority of the neighbors of $v$ are in $S$, or equivalently, every vertex $v\in\overline{S}$ has more neighbors in $S$ than it has in $\overline{S}$. A set of vertices $S\subseteq V$ in a graph $G=(V,E)$ is called a total majority set if for every vertex $v\in V$, a majority of the neighbors of $v$ are in $S$, or equivalently, every vertex $v\in V$ has more neighbors in $S$ than it has in $\overline{S}$. In this paper we show that majority sets in graphs are closely related to, but different than, a variety of sets that have been studied, such as offensive alliances, cost effective and very cost effective sets and unfriendly partitions in graphs. We also prove that the decision problems associated with external majority sets and total majority sets are NP-complete. Finally, we present a list of open problems related to majority sets in graphs. https://comb-opt.azaruniv.ac.ir/article_15062_7a76026083da7727f55d23a2eca85043.pdf