2023/07/02 by Davood Bakhshesh, Bakhshesh, Davood, Michael A. Henning +1 · 1 citation
Computer Science · #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2307.01222
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 = \X1,…,Xk\ of the vertex set V(G) of G such that for all i ∈ [k], each set Xi ∈ X satisfies one of the following two conditions: (1) Xi is a dominating set of G with a single vertex, or (2) Xi forms a coalition with some other set Xj ∈ X. %The coalition number C(G) is the maximum cardinality of a c-partition of G. Let \cal A = \A1,…,Ar\ and \cal B= \B1,…, Bs\ be two partitions of V(G). Partition \cal B is a refinement of partition \cal A if every set Bi ∈ \cal B is either equal to, or a proper subset of, some set Aj ∈ \cal A. Further if \cal A ≠ \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 cmin(G) of G to equal the minimum order of a minimal c-partition of G. We show that 2 ≤ cmin(G) ≤ n, and we characterize graphs G of order n satisfying cmin(G) = n. A polynomial-time algorithm is given to determine if cmin(G)=2 for a given graph G. A necessary and sufficient condition for a graph G to satisfy cmin(G) ≥ 3 is given, and a characterization of graphs G with minimum degree~2 and cmin(G)= 4 is provided.