COMPLEMENTARY COALITION GRAPHS: CHARACTERIZATION AND ALGORITHM

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. Given a coalition partition X of a graph G, a coalition graph CG(G, X) is constructed by representing each member of X as a vertex of the graph, and joining two vertices with an edge if and only if the corresponding sets form a coalition in G. If each set in a coalition partition X of G contains only one vertex, then X is referred to as a singleton coalition partition. A graph G is a complementary coalition graph if CG(G, X) is isomorphic to the complement of G. We characterize complementary coalition graphs. This solves an open problem posed by Haynes et al. [Commun. Comb. Optim. 8 (2023) 423–430]. Moreover, we provide a polynomial-time algorithm that determines if a given graph is a complementary coalition graph.