| تعداد نشریات | 6 |
| تعداد شمارهها | 121 |
| تعداد مقالات | 1,448 |
| تعداد مشاهده مقاله | 1,555,853 |
| تعداد دریافت فایل اصل مقاله | 1,459,870 |
Majority Sets in Graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 12 آذر 1404 اصل مقاله (467.32 K) | ||
| نوع مقاله: Special issue of CCO to honor Odile Favaron | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.30739.2602 | ||
| نویسندگان | ||
| Mustapha Chellali* 1؛ Stephen T. Hedetniemi2؛ Nacéra Meddah1 | ||
| 1AMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria | ||
| 2Professor 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. | ||
| کلیدواژهها | ||
| minority sets, 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. | ||
|
آمار تعداد مشاهده مقاله: 48 تعداد دریافت فایل اصل مقاله: 76 |
||