A set $S$ of vertices in a graph $G$ is a dominating set if every vertex of $V(G) \setminus 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 \cup 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 $\mathcal{ X} = \{ X_1,\ldots,X_k\}$ of the vertex set $V(G)$ of $G$ such that for all $i \in [k]$, each set $X_i \in \mathcal{ 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 \in \mathcal{ X}$. %The coalition number ${ C}(G)$ is the maximum cardinality of a $c$-partition of $G$. Let ${ \cal A} = \{ A_1,\ldots,A_r\}$ and ${ \cal B}= \{ B_1,\ldots, B_s\}$ be two partitions of $V(G)$. Partition ${ \cal B}$ is a refinement of partition ${ \cal A}$ if every set $B_i \in { \cal B} $ is either equal to, or a proper subset of, some set $A_j \in { \cal A}$. Further if ${ \cal A} \ne { \cal B}$, then ${ \cal B}$ is a proper refinement of ${ \cal A}$. Partition ${ \cal 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 \le c_{ \min}(G) \le 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) \ge 3$ is given, and a characterization of graphs $G$ with minimum degree~$2$ and $c_{ \min}(G)= 4$ is provided.
Categories: math.CO cs.DM