Perfect coalition in graphs

Abstract

\noindent A perfect dominating set in a graph $G=(V,E)$ is a subset $S\subseteq V$ such that each vertex in $V\setminus S$ has exactly one neighbor in $S$. A perfect coalition in $G$ consists of two disjoint sets of vertices $V_i$ and $V_j$ such that i) neither $V_i$ nor $V_j$ is a dominating set, ii) each vertex in $V(G)\setminus V_i$ has at most one neighbor in $V_i$ and each vertex in $V(G)\setminus V_j$ has at most one neighbor in $V_j$, and iii) $V_i\cup V_j$ is a perfect dominating set. A perfect coalition partition (abbreviated $prc$-partition) in a graph $G$ is a vertex partition $\ddot{I}€=\{V_1,V_2,\dots ,V_k\}$ such that for each set $V_i$ of $\ddot{I}€$ either $V_i$ is a singleton dominating set, or there exists a set $V_j\in \ddot{I}€$ that forms a perfect coalition with $V_i$. In this paper, we initiate the study of perfect coalition partitions in graphs. We obtain a bound on the number of perfect coalitions involving each member of a perfect coalition partition, in terms of maximum degree. The perfect coalition of some special graphs are investigated. The graph $G$ with $\hat{I}´(G)=1$, the triangle-free graphs $G$ with prefect coalition number of order of $G$ and the trees $T$ with prefect coalition number in $\{n,n-1,n-2\}$ where $n=|V(T)|$ are characterized.

18 pages