Coalition Graphs

Document Type : Original paper

Authors

1 East Tennessee State University; Department of Mathematics University of Johannesburg

2 Florida Atlantic University

3 Professor Emeritus Clemson University Clemson, South Carolina

4 Appalachian State University

Abstract

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.

Keywords

Main Subjects

References

[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.
Communications in Combinatorics and Optimization
Volume 8, Issue 2
June 2023
Pages 423-430

Files

Share

How to cite

Statistics