The minmin coalition number in graphs

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₁,…,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₁,…,A_r} and B={B₁,…,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.