Majority sets in graphs

Chellali, Mustapha; Hedetniemi, Stephen T.; Meddah, Nacéra

doi:10.22049/cco.2025.30739.2602

تعداد نشریات	6
تعداد شماره‌ها	125
تعداد مقالات	1,584
تعداد مشاهده مقاله	1,747,132
تعداد دریافت فایل اصل مقاله	1,624,149

	Majority sets in graphs
Communications in Combinatorics and Optimization
مقاله 5، دوره 11، شماره 4، اسفند 2026، صفحه 1107-1123 اصل مقاله (466.56 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2025.30739.2602
نویسندگان
Mustapha Chellali^* ¹؛ Stephen T. Hedetniemi²؛ Nacéra Meddah¹
¹AMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
²Professor and Chair Emeritus of Computer Science, Clemson University, Clemson, SC 29634 USA
چکیده
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.
کلیدواژه‌ها
majority sets؛ independent sets؛ hereditary properties؛ dominating sets in graphs

مراجع
[1] R. Aharoni, E.C. Milner, and K. Prikry, Unfriendly partitions of a graph, J. Comb. Theory, B 50 (1990), no. 1, 1–10. https://doi.org/10.1016/0095-8956(90)90092-E [2] C. Bazgan, Z. Tuza, and D. Vanderpooten, The satisfactory partition problem, Discrete Appl. Math. 154 (2006), no. 8, 1236–1245. https://doi.org/10.1016/j.dam.2005.10.014 [3] O.V. Borodin and A.V. Kostochka, On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density, J. Comb. Theory, B 23 (1977), no. 2-3, 247–250. https://doi.org/10.1016/0095-8956(77)90037-5 [4] M. Chellali, T.W. Haynes, and S.T. Hedetniemi, Client–server and cost effective sets in graphs, AKCE Int. J. Graphs Comb. 15 (2018), no. 2, 211–218. https://doi.org/10.1016/j.akcej.2017.09.001 [5] M. Chellali, S.T. Hedetniemi, and N. Meddah, Minority sets in graphs, Aequationes Math. 99 (2025), no. 4, 1935–1954. https://doi.org/10.1007/s00010-025-01178-1 [6] E.J. Cockayne, P.J.P. Grobler, S.T. Hedetniemi, and A.A. McRae, What makes an irredundant set maximal?, J. Combin. Math. Combin. Comput. (1997), 213–224. [7] E.J. Cockayne, J.H. Hattingh, S.M. Hedetniemi, S.T. Hedetniemi, and A.A. McRae, Using maximality and minimality conditions to construct inequality chains, Discrete Math. 176 (1997), no. 1-3, 43–61. https://doi.org/10.1016/S0012-365X(96)00356-1 [8] E.J. Cockayne, S.T. Hedetniemi, and D.J. Miller, Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull. 21 (1978), no. 4, 461–468. https://doi.org/10.4153/CMB-1978-079-5 [9] F. Dahme, D. Rautenbach, and L. Volkmann, Some remarks on $\alpha$-domination, Discuss. Math. Graph Theory 24 (2004), no. 3, 423–430. [10] J.E. Dunbar, D.G. Hoffman, R.C. Laskar, and L.R. Markus, α-domination, Discrete Math. 211 (2000), no. 1-3, 11–26. https://doi.org/10.1016/S0012-365X(99)00131-4 [11] M.U. Gerber and D. Kobler, Partitioning a graph to satisfy all vertices, Tech. report, Swiss Federal Inst. Tech., Lausanne, 1998. [12] M.U. Gerber and D. Kobler, Algorithmic approach to the satisfactory graph partitioning problem, Eur. J. Oper. Res. 125 (2000), no. 2, 283–291. https://doi.org/10.1016/S0377-2217(99)00459-2 [13] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, CRC press, 2013. [14] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, T.L. McCoy, and I. Vasylieva, Cost effective domination in graphs., Congr. Numer. 211 (2012), 197–209. [15] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Global defensive alliances in graphs, Electron. J. Comb. 10 (2003), R47. https://doi.org/10.37236/1740 [16] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Global Defensive Alliances, Proc. 17th Int. Symp. Comput. Inform. Sci., I, ISCIS XVII (Orlando, FL, 2002), CRC Press, 2022, pp. 303–307. [17] T.W. Haynes, S.T. Hedetniemi, T.L. McCoy, and T.K. Rodriguez, Bounds on cost effective domination numbers, Quaest. Math. 39 (2016), no. 6, 773–783. https://doi.org/10.2989/16073606.2016.1167133 [18] T.W. Haynes, S.T. Hedetniemi, and I. Vasylieva, Very cost effective bipartitions in graphs, AKCE Int. J. Graphs Comb. 12 (2015), no. 2-3, 155–160. https://doi.org/10.1016/j.akcej.2015.11.009 [19] T.W. Haynes, J.A. Lachniet, and S. Arumugam, The alliance partition number of grid graphs, AKCE Int. J. Graphs Comb. 4 (2007), no. 1, 51–59. https://doi.org/10.1080/09728600.2007.12088820 [20] S.M. Hedetniemi, S.T. Hedetniemi, R. Laskar, H.M. Mulder, and S. Arumugam, Quorum colorings of graphs, AKCE Int. J. Graphs Comb. 10 (2013), no. 1, 97–109. https://doi.org/10.1080/09728600.2013.12088727 [21] S.T. Hedetniemi, A.A. McRae, and R. Mohan, The private neighbor concept, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer International Publishing, Cham, 2021, pp. 183–218. https://doi.org/10.1007/978-3-030-58892-2_7 [22] G. Hickey, F. Dehne, A. Rau-Chaplin, and C. Blouin, SPR distance computation for unrooted trees, Evol. Bioinform. 4 (2008), 17–27. [23] C.M. Mynhardt and A. Roux, Irredundance, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer International Publishing, Cham, 2021, pp. 135–181. https://doi.org/10.1007/978-3-030-58892-2_6 [24] J.A. Rodriguez-Velazquez, J.M. Sigarreta, and O. Favaron, Global alliances in planar graphs, AKCE Int. J. Graphs Comb. 4 (2007), no. 1, 83–98. https://doi.org/10.1080/09728600.2007.12088822 [25] K.H. Shafique and R.D. Dutton, On satisfactory partitioning of graphs, Congr. Numer. 154 (2002), 183–194. [26] S. Shelah and E.C. Milner, Graphs with no unfriendly partitions, A tribute to Paul Erd¨os (1990), 373–384.
آمار تعداد مشاهده مقاله: 293 تعداد دریافت فایل اصل مقاله: 300

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

Majority sets in graphs