Abstract
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 subset of V(G)is a double dominating set of G, if every vertex in V(G)\Shas 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 boolean OR 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 psi={V-1, V-2,..., V-k}such that for all i is an element of[k],the set V-i forms a double coalition with another set V-j for some j, where j is an element of[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)>= delta(G)+1 where delta(G)denotes the minimum degree among the vertices of G. We show that if delta(G)is an element of{1,2}, then DC(G)<=Delta(G)+1 where Delta(G)denotes the maximum degree among the vertices of G. However we show that there exist graphs G with delta(G) >= 6 satisfying DC(G)>Delta(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