On Coalition Graphs and Coalition Count of Graphs

Abstract

Let $G$ be graph with vertex set $V(G)$ and order $n$. A coalition in a graph $G$ consists of two disjoint sets of vertices $V_1$ and $V_2$, neither of which is a dominating set but whose union $V_1\cup V_2$ is a dominating set. A coalition partition, abbreviated $c$-partition, in a graph $G$ is a vertex partition $\ddot{I}€=\left\{V_1,V_2,\dots ,V_k\right\}$ such that every set $V_i$ of $\ddot{I}€$ is either a singleton dominating set, or is not a dominating set but forms a coalition with another set $V_j$ in $\ddot{I}€$. The sets $V_i$ and $V_j$ are coalition partners in $G$. The coalition number $C(G)$ equals the maximum order $k$ of a $c$-partition of $G$. For any graph $G$ with a $c$-partition $\ddot{I}€=\left\{V_1,V_2,\dots ,V_k\right\}$, the coalition graph $CG(G,\ddot{I}€)$ of $G$ is a graph with vertex set $V_1,V_2,\dots ,V_k$, corresponding one-to-one with the set $\ddot{I}€$, and two vertices $V_i$ and $V_j$ are adjacent in $CG(G,\ddot{I}€)$ if and only if the sets $V_i$ and $V_j$ are coalition partners in $\ddot{I}€$. In [4], authors proved that for every graph $G$ there exist a graph $H$ and $c$-partition $\ddot{I}€$ such that $CG(H,\ddot{I}€)\cong G$, and raised the question: Does there exist a graph $H^{\ast }$ of smaller order $n^{\ast }$ and size $m^{\ast }$ with a $c$-partition $\ddot{I}{€}^{\ast }$ such that $CG(H^{\ast },\ddot{I}{€}^{\ast })\cong G$?. In this paper, we constructed a graph $H^{\ast }$ of small order and size and a $c$- partition $\ddot{I}{€}^{\ast }$ such that $CG(H^{\ast },\ddot{I}{€}^{\ast })\cong G$. Recently, Haynes et al.[5] defined the coalition count $c(G)$ of a graph $G$ as the maximum number of different coalition in any $c$-partition of $G$. We characterize all graphs $G$ with $c(G)=1$. Further, imposing some suitable conditions on coalition number, we study the properties of coalition count of graph.