Opuscula Math. 43, no. 2 (2023), 173-183
https://doi.org/10.7494/OpMath.2023.43.2.173
Opuscula Mathematica
Self-coalition graphs
Teresa W. Haynes
Jason T. Hedetniemi
Stephen T. Hedetniemi
Alice A. McRae
Raghuveer Mohan
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\) which is not a dominating set. 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. The singleton partition \(\pi_1\) of the vertex set of \(G\) is a partition of order \(|V|\), that is, each vertex of \(G\) is in a singleton set of the partition. A graph \(G\) is called a self-coalition graph if \(G\) is isomorphic to its coalition graph \(CG(G,\pi_1)\), where \(\pi_1\) is the singleton partition of \(G\). In this paper, we characterize self-coalition graphs.
Keywords: coalitions in graphs, coalition partitions, coalition graphs, domination.
Mathematics Subject Classification: 05C69.
- T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, R. Mohan, Introduction to coalitions in graphs, AKCE Int. J. Graphs Combin. 17 (2020), no. 2, 653-659. https://doi.org/10.1080/09728600.2020.1832874
- T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, R. Mohan, Upper bounds on the coalition number, Austral. J. Combin. 80 (2021), no. 3, 442-453.
- T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, R. Mohan, Coalition graphs of paths, cycles, and trees, Discuss. Math. Graph Theory, in press. https://doi.org/10.7151/dmgt.2416
- T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, R. Mohan, Coalition graphs, Comm. Combin. Optim. 8 (2023), no. 2, 423-430.
- Teresa W. Haynes (corresponding author)
- East Tennessee State University, Department of Mathematics and Statistics, Johnson City, TN 37614, USA
- University of Johannesburg, Department of Mathematics, Auckland Park, South Africa
- Jason T. Hedetniemi
- Department of Mathematics, Wilkes Honors College, Florida Atlantic University, Jupiter, FL 33458, USA
- Stephen T. Hedetniemi
- Professor Emeritus, Clemson University, School of Computing, Clemson, SC 29634, USA
- Alice A. McRae
- Appalachian State University, Computer Science Department, Boone, NC 28608, USA
- Raghuveer Mohan
- Appalachian State University, Computer Science Department, Boone, NC 28608, USA
- Communicated by Andrzej Żak.
- Received: 2022-07-06.
- Revised: 2022-12-14.
- Accepted: 2022-12-16.
- Published online: 2023-03-27.
