On the connected coalition number of graphs
Xiaxia Guan, Maoqun Wang · Journal of Combinatorial Mathematics and Combinatorial Computing · 2025
For a graph \(G=(V,E)\), a pair of vertex disjoint sets \(A_{1}\) and \(A_{2}\) form a connected coalition of \(G\), if \(A_{1}\cup A_{2}\) is a connected dominating set, but neither \(A_{1}\) nor \(A_{2}\) is a connected dominating set. A connected coalition partition of \(G\) is a partition \(\Phi\) of \(V(G)\) such that each set in \(\Phi\) either consists of only a singe vertex with the degree \(\mid V(G)\mid-1\), or forms a connected coalition of \(G\) with another set in \(\Phi\). The connected coalition number of \(G\), denoted by \(CC(G)\), is the largest possible size of a connected coalition partition of \(G\). In this paper, we characterize graphs that satisfy \(CC(G)=2\). Moreover, we obtain the connected coalition number for unicycle graphs and for the corona product and join of two graphs. Finally, we give a lower bound on the connected coalition number of the Cartesian product and the lexicographic product of two graphs.