Strong coalitions in graphs

Abstract

For a graph $G=(V,E)$, a set $D\subset V(G)$ is a strong dominating set of $G$, if for every vertex $x\in V(G)\setminus D$ there is a vertex $y\in D$ with $xy\in E(G)$ and $deg(x)\le deg(y)$. A strong coalition consists of two disjoint sets of vertices $V_1$ and $V_2$, neither of which is a strong dominating set but whose union $V_1\cup V_2$, is a strong dominating set. A vertex partition $\hat{I}\text{c◯}=\{V_1,V_2,...,V_k\}$ of vertices in $G$ is a strong coalition partition, if every set $V_i\in \hat{I}\text{c◯}$ either is a strong dominating set consisting of a single vertex of degree $n-1$, or is not a strong dominating set but produces a strong coalition with another set $V_j\in \hat{I}\text{c◯}$ that is not a strong dominating set. The maximum cardinality of a strong coalition partition of $G$ is the strong coalition number of $G$ and is denoted by $SC(G)$. In this paper, we study properties of strong coalitions in graphs.

14 pages, 1 figure