Introduction to double coalitions in graphs

Abstract

Let $G(V,E)$ be a finite, simple, isolate-free graph. A set $D$ of vertices of a graph $G$ with the vertex set $V$ is a double dominating set of $G$, if every vertex $v\in D$ has at least one neighbor in $D$ and every vertex $v\in V\setminus D$ has at least two neighbors in $D$. A double coalition consists of two disjoint sets of vertices $V_1$ and $V_2$, neither of which is a double dominating set but their union $V_1\cup V_2$ is a double dominating set. A double coalition partition of a graph $G$ is a partition $\Pi =\{V_1,V_2,...,V_k\}$ of $V$ such that no subset of $\Pi$ is a double dominating set of $G$, but for every set $V_i\in \Pi$, there exists a set $V_j\in \Pi$ such that $V_i$ and $V_j$ form a double coalition. In this paper, we study properties of double coalitions in graphs.