Double Coalitions in Graphs

A set S of vertices in a graph G is a dominating set of G if every vertex not in S has a neighbor in S, where two vertices are neighbors if they are adjacent. If G is isolate-free, then a set S⊆V(G) is a double dominating set of G, if every vertex in V(G)\S has at least two neighbors in S, and every vertex in S has a neighbor in S. A double coalition in G consists of two disjoint sets of vertices X and Y of G, neither of which is a double dominating set but whose union X∪Y is a double dominating set of G. Such sets X and Y are said to form a double coalition. A double coalition partition in G is a vertex partition Ψ={V1,V2,…,Vk} such that for all i∈[k], the set Vi forms a double coalition with another set Vj for some j, where j∈[k]\{i}. The double coalition number, DC(G), of G equals the maximum order of a double coalition partition in G. We prove that every isolate-free graph has a double coalition partition, and we show that 2≤DC(G)≤n and we characterize the graphs G satisfying DC(G)=2 and the graphs G satisfying DC(G)=n. We show that DC(G)≥δ(G)+1 where δ(G) denotes the minimum degree among the vertices of G. We show that if δ(G)∈{1,2}, then DC(G)≤Δ(G)+1 where Δ(G) denotes the maximum degree among the vertices of G. However we show that there exist graphs G with δ(G)≥6 satisfying DC(G)>Δ(G)+1. We determine the double coalition number of special classes of graphs. In particular, we determine the double coalition number of every cubic graph G and show that DC(G)=4 always holds.