2025/09/18 by Nazli Besharati, Doost Ali Mojdeh, Besharati, Nazli +3
Economics, Econometrics and Finance · #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2509.15386
Let G=(V,E) be a graph. A subset S ⊆ V is called a global dominating set of G, if it serves as a dominating set in both G and its complement G. We define two disjoint subsets V1,V2 ⊆ V to form a global coalition if neither V1 nor V2 individually constitutes a global dominating set, yet their union V1 ∪ V2 does. A global coalition partition (abbreviated as gc-partition) of G is a vertex partition π of V(G) such that for every subset Vi ∈ π, there exists another subset Vj ∈ π with which Vi forms a global coalition. In this paper, we initiate the study of global coalition in graphs. Specifically, we prove that every graph admits a gc-partition. Additionally, we establish an upper bound on the number of global coalitions in which each member of a gc-partition can participate. We also explore the relationships between global coalition and coalition, as well as between global coalition and perfect coalition in graphs. Finally, we explore properties of gc-partitions in unicyclic graphs.