Secure coalitions in graphs

Abstract

A secure coalition in a graph $G$ consists of two disjoint vertex sets $V_1$ and $V_2$, neither of which is a secure dominating set, but whose union $V_1\cup V_2$ forms a secure dominating set. A secure coalition partition ($sec$-partition) of $G$ is a vertex partition $\ddot{I}€=\{V_1,V_2,\dots ,V_k\}$ where each set $V_i$ is either a secure dominating set consisting of a single vertex of degree $n-1$, or a set that is not a secure dominating set but forms a secure coalition with some other set $V_j\in \ddot{I}€$. The maximum cardinality of a secure coalition partition of $G$ is called the secure coalition number of $G$, denoted $SEC(G)$. For every $sec$-partition $\ddot{I}€$ of a graph $G$, we associate a graph called the secure coalition graph of $G$ with respect to $\ddot{I}€$, denoted $SCG(G,\ddot{I}€)$, where the vertices of $SCG(G,\ddot{I}€)$ correspond to the sets $V_1,V_2,\dots ,V_k$ of $\ddot{I}€$, and two vertices are adjacent in $SCG(G,\ddot{I}€)$ if and only if their corresponding sets in $\ddot{I}€$ form a secure coalition in $G$. In this study, we prove that every graph admits a $sec$-partition. Further, we characterize the graphs $G$ with $SEC(G)\in \{1,2,n\}$ and all trees $T$ with $SEC(T)=n-1$. Finally, we show that every graph $G$ without isolated vertices is a secure coalition graph.