## Abstract

A set S of vertices in a graph G is a dominating set if every vertex of V(G)\S is adjacent to a vertex in S. A coalition in G consists of two disjoint sets of vertices X and Y of G, neither of which is a dominating set but whose union X∪Y is a dominating set of G. Such sets X and Y form a coalition in G. A coalition partition, abbreviated c-partition, in G is a partition X={X_{1},…,X_{k}} of the vertex set V(G) of G such that for all i∈[k], each set X_{i}∈X satisfies one of the following two conditions: (1) X_{i} is a dominating set of G with a single vertex, or (2) X_{i} forms a coalition with some other set X_{j}∈X. Let A={A_{1},…,A_{r}} and B={B_{1},…,B_{s}} be two partitions of V(G). Partition B is a refinement of partition A if every set B_{i}∈B is either equal to, or a proper subset of, some set A_{j}∈A. Further if A≠B, then B is a proper refinement of A. Partition A is a minimal c-partition if it is not a proper refinement of another c-partition. Haynes et al. [AKCE Int. J. Graphs Combin. 17 (2020), no. 2, 653–659] defined the minmin coalition number c_{min}(G) of G to equal the minimum order of a minimal c-partition of G. We show that 2≤c_{min}(G)≤n, and we characterize graphs G of order n satisfying c_{min}(G)=n. A polynomial-time algorithm is given to determine if c_{min}(G)=2 for a given graph G. A necessary and sufficient condition for a graph G to satisfy c_{min}(G)≥3 is given, and a characterization of graphs G with minimum degree 2 and c_{min}(G)=4 is provided.

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

Journal | Aequationes Mathematicae |

DOIs | |

Publication status | Accepted/In press - 2024 |

## Keywords

- 05C69
- 68Q25
- Coalition number
- Coalition partition
- Dominating set
- Domination number

## ASJC Scopus subject areas

- General Mathematics
- Discrete Mathematics and Combinatorics
- Applied Mathematics