Connected coalitions in graphs
Saeid Alikhani, Davood Bakhshesh, Hamidreza Golmohammadi, Elena V. Konstantinova · Discussiones Mathematicae Graph Theory · 2023
Let G = (V, E) be a graph, and define a connected coalition as a pair of disjoint vertex sets U 1 and U 2 such that U 1 ∪ U 2 forms a connected dominating set, but neither U 1 nor U 2 individually forms a connected dominating set.A connected coalition partition of G is a partition Φ = {U 1 , U 2 , . . ., U k } of the vertices such that each set U i ∈ Φ either consists of only a single vertex with degree n -1, or forms a connected coalition with another set U j ∈ Φ that is not a connected dominating set.The connected coalition number CC(G) is defined as the largest possible size of a connected coalition partition for G.The objective of this study is to initiate an examination into the notion of connected coalitions in graphs and present essential findings.More precisely, we provide a thorough characterization of all graphs possessing a connected coalition partition.Moreover, we establish that, for any graph G with order n, a minimum degree of 1, and no full vertex, the condition CC(G) < n holds.In addition, we prove that any tree T achieves 2 S. Alikhani, D. Bakhshesh, H.R. Golmohammadi, E.V. Konstantinova CC(T ) = 2. Lastly, we propose two polynomial-time algorithms that determine whether a given connected graph G of order n satisfies CC(G) = n or CC(G) = n -1.