تعداد نشریات | 5 |
تعداد شمارهها | 108 |
تعداد مقالات | 1,228 |
تعداد مشاهده مقاله | 1,147,105 |
تعداد دریافت فایل اصل مقاله | 1,006,026 |
Coalition Graphs | ||
Communications in Combinatorics and Optimization | ||
مقاله 11، دوره 8، شماره 2، شهریور 2023، صفحه 423-430 اصل مقاله (341.07 K) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2022.27916.1394 | ||
نویسندگان | ||
Teresa W. Haynes* 1؛ Jason T. Hedetniemi2؛ Stephen T Hedetniemi3؛ Alice McRae4؛ Raghuveer Mohan4 | ||
1East Tennessee State University; Department of Mathematics University of Johannesburg | ||
2Florida Atlantic University | ||
3Professor Emeritus Clemson University Clemson, South Carolina | ||
4Appalachian State University | ||
چکیده | ||
A coalition in a graph $G = (V, E)$ consists of two disjoint sets $V_1$ and $V_2$ of vertices, such that neither $V_1$ nor $V_2$ is a dominating set, but the union $V_1 \cup V_2$ is a dominating set of $G$. A coalition partition in a graph $G$ of order $n = |V|$ is a vertex partition $\pi = {V_1, V_2, \ldots, V_k}$ such that every set $V_i$ either is a dominating set consisting of a single vertex of degree $n-1$, or is not a dominating set but forms a coalition with another set $V_j$. Associated with every coalition partition $\pi$ of a graph $G$ is a graph called the coalition graph of $G$ with respect to $\pi$, denoted $CG(G,\pi)$, the vertices of which correspond one-to-one with the sets $V_1, V_2, \ldots, V_k$ of $\pi$ and two vertices are adjacent in $CG(G,\pi)$ if and only if their corresponding sets in $\pi$ form a coalition. In this paper, we initiate the study of coalition graphs and we show that every graph is a coalition graph. | ||
کلیدواژهها | ||
Dominating set؛ Coalition؛ Independent dominating set | ||
مراجع | ||
[1] J.-C. Bermond, J. Bond, D. Peleg, and S. Perennes, The power of small coalitions in graphs, Discrete Appl. Math. 127 (2003), no. 3, 399–414.
[2] Teresa W Haynes, Jason T Hedetniemi, Stephen T Hedetniemi, Alice A McRae, and Raghuveer Mohan, Coalition graphs of paths, cycles, and trees., Discuss. Math. Graph Theory (In press).
[3] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R. Mohan, Introduction to coalitions in graphs, AKCE Int. J. Graphs Combin. 17 (2020), no. 2, 653–659.
[4] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R. Mohan, Upper bounds on the coalition number, Austral. J. Combin. 80 (2021), no. 3, 442–453.
[5] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R. Mohan, Self-coalition graphsr, (Submitted).
[6] H. Monsuur and R.H.P. Janssen, Structural stability of coalitions: A formal model highlighting the role of participants positioned between members and neutral actors, Games 13 (2022), no. 1, 17.
[7] D. Peleg, Local majorities, coalitions and monopolies in graphs: a review, Theoret. Comput. Sci. 282 (2002), no. 2, 231–257.
[8] T. Voice, M. Polukarov, and N.R. Jennings, Coalition structure generation over graphs, J. Artif. Intell. 45 (2012), no. 1, 165–196. | ||
آمار تعداد مشاهده مقاله: 893 تعداد دریافت فایل اصل مقاله: 1,508 |