Double Coalitions in Graphs
Michael A. Henning, Doost Ali Mojdeh · Bulletin of the Malaysian Mathematical Sciences Society · 2025
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 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 \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 prove that every isolate-free graph has a double coalition partition, and we show that $$2 \le \textrm{DC}(G) \le n$$ 2 ≤ DC ( G ) ≤ n and we characterize the graphs G satisfying $$\textrm{DC}(G) = 2$$ DC ( G ) = 2 and the graphs G satisfying $$\textrm{DC}(G) = n$$ DC ( G ) = n . We show that $$\textrm{DC}(G) \ge \delta (G) + 1$$ DC ( G ) ≥ δ ( G ) + 1 where $$\delta (G)$$ δ (