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.

Full text (pdf)

1. 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
2. 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.
3. 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
4. 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.
• Revised: 2022-12-14.
• Accepted: 2022-12-16.
• Published online: 2023-03-27.