## Abstract

Let G be a graph with vertex set V and order n=|V|. A coalition in G is a combination of two distinct sets, A⊆V and B⊆V, which are disjoint and are not dominating sets of G, but their union A∪B is a dominating set of G. A coalition partition of G is a partition P={S_{1},…,S_{k}} of its vertex set V, where each set S_{i}∈P is either a dominating set of G with only one vertex, or it is not a dominating set but forms a coalition with some other set S_{j}∈P. The coalition number C(G) is the maximum cardinality of a coalition partition of G. To represent a coalition partition P of G, a coalition graph CG(G,P) is created, where each vertex of the graph corresponds to a member of P and two vertices are adjacent if and only if their corresponding sets form a coalition in G. A coalition partition P of G is a singleton coalition partition if every set in P consists of a single vertex. If a graph G has a singleton coalition partition, then G is referred to as a singleton-partition graph. A graph H is called a singleton coalition graph of a graph G if there exists a singleton coalition partition P of G such that the coalition graph CG(G,P) is isomorphic to H. A singleton coalition graph chain with an initial graph G_{1} is defined as the sequence G_{1}→G_{2}→G_{3}→⋯ where all graphs G_{i} are singleton-partition graphs, and CG(G_{i},Γ_{1})=G_{i+1}, where Γ_{1} represents a singleton coalition partition of G_{i}. In this paper, we address two open problems posed by Haynes et al. We characterize all graphs G of order n and minimum degree δ(G)=2 such that C(G)=n. Additionally, we investigate the singleton coalition graph chain starting with graphs G, where δ(G)≤2.

Original language | English |
---|---|

Article number | 85 |

Journal | Computational and Applied Mathematics |

Volume | 43 |

Issue number | 2 |

DOIs | |

Publication status | Published - Mar 2024 |

## Keywords

- Coalition graphs
- Coalition number
- Coalition partition
- Domination number

## ASJC Scopus subject areas

- Computational Mathematics
- Applied Mathematics