Double Coalitions in Regular Graphs

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 \subseteq V(G)$$ S ⊆ V ( G ) is a double dominating set of G if every vertex in $$V(G) \setminus S$$ 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 \cup Y$$ 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 $$\Psi = \{V_1,V_2,\ldots ,V_k\}$$ Ψ = { V 1 , V 2 , … , V k } such that for all $$i \in [k]$$ i ∈ [ k ] , the set $$V_i$$ V i forms a double coalition with another set $$V_j$$ V j for some j, where $$j \in [k] \setminus \{i\}$$ j ∈ [ k ] \ { i } . The double coalition number, $$\textrm{DC}(G)$$ 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 $$\theta _{r}^{\textrm{reg}}$$ θ r reg and $$\theta _{r}$$ θ r (which depend only on r) for each $$r \ge 3$$ r ≥ 3 , such that $$\textrm{DC}(G) \le \theta _{r}^{\textrm{reg}} \times r$$ DC ( G ) ≤ θ r reg × r for the class of r-regular graphs G and $$\textrm{DC}(G) \le \theta _{r} \times \Delta (G)$$ DC ( G ) ≤ θ r × Δ ( G ) for the class of graphs G with minimum degree equal to r. We show that $$\theta _{r}^{\textrm{reg}} \ge 2 \left( \frac{r-1}{r} \right) $$ θ r reg ≥ 2 r - 1 r for all $$r \ge 3$$ r ≥ 3 , and that equality holds if $$r \in \{3,4\}$$ r ∈ { 3 , 4 } , while $$\theta _{r} \ge 2$$ θ r ≥ 2 for all $$r \ge 3$$ r ≥ 3 , and $$\theta _{r} \ge 3$$ θ r ≥ 3 for r sufficiently large. Moreover, we show that $$\theta _3 = 2$$ θ 3 = 2 . Finally, we prove that $$5 \le \textrm{DC}(G) \le 6$$ 5 ≤ DC ( G ) ≤ 6 whenever G is a 4-regular graph.