Double Coalitions in Regular 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 at least one 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 discuss the problem to determine or estimate the best possible constants θrreg and θr (which depend only on r) for each r≥3, such that DC(G)≤θrreg×r for the class of r-regular graphs G and DC(G)≤θr×Δ(G) for the class of graphs G with minimum degree equal to r. We show that θrreg≥2r-1r for all r≥3, and that equality holds if r∈{3,4}, while θr≥2 for all r≥3, and θr≥3 for r sufficiently large. Moreover, we show that θ3=2. Finally, we prove that 5≤DC(G)≤6 whenever G is a 4-regular graph.