Majority Sets in Graphs

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

1 AMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria

2 Professor and Chair Emeritus of Computer Science, Clemson University, Clemson, SC 29634 USA

Abstract

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.

Keywords

Main Subjects

References

[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.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 03 December 2025

Files

Share

How to cite

Statistics