Connecting Coalition Partitions in the Cartesian Product of Graphs

For a graph G, the vertex partition σ =₁, V₂,⋯ , Vₖ\ is a connecting coalition partition if each Vᵢ ∈ σ , |Vᵢ| > 1 , induces a disconnected graph but a union with some Vⱼ ∈ σ , |Vⱼ| > 1 , Vᵢ ∪ Vⱼ induces a connected graph; otherwise Vᵢ ∈ σ is a singleton set containing a full vertex of G in σ . Among all possible connecting coalition partitions for a graph G, the cardinality of the partition σ having the maximum value is the connecting coalition number, ζ (G) . In this article, we determine the connecting coalition number for the Cartesian product of graphs. For graphs GF , that do not attain a connecting coalition partition, the connecting coalition partition for GF G , with a given graph G, is determined. The existence of the connecting coalition partition for the Cartesian product of any two non-trivial graphs is proved.