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.
  • Received: 2022-07-06.
  • Revised: 2022-12-14.
  • Accepted: 2022-12-16.
  • Published online: 2023-03-27.
Opuscula Mathematica - cover

Cite this article as:
Teresa W. Haynes, Jason T. Hedetniemi, Stephen T. Hedetniemi, Alice A. McRae, Raghuveer Mohan, Self-coalition graphs, Opuscula Math. 43, no. 2 (2023), 173-183, https://doi.org/10.7494/OpMath.2023.43.2.173

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

We advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.