Global coalitions in graphs

Abstract

Let $G=(V,E)$ be a graph. A subset $S\subseteq V$ is called a global dominating set of $G$ if it is a dominating set of both $G$ and its complement $\overline{G}$. Two disjoint subsets $V_1,V_2\subseteq V$ form a global coalition if neither $V_1$ nor $V_2$ is a global dominating set, but their union $V_1\cup V_2$ is. A global coalition partition (abbreviated $gc$-partition) of $G$ is a vertex partition $\pi$ of $V(G)$ such that every class of $\pi$ forms a global coalition with some other class of $\pi$. The global coalition number $GC(G)$ is the maximum cardinality of a $gc$-partition of $G$. In this paper, we initiate the study of these concepts. We prove that every graph of order at least two admits a $gc$-partition, give general lower bounds on $GC(G)$, and bound the number of global coalitions in which a single class of a $gc$-partition can be involved. We show that $GC(G)$ coincides with the coalition number $C(G)$ whenever $G$ is disconnected or has radius at least three, and consequently that $GC(G)=C(\overline{G})$ for every join of two graphs. We determine the global coalition number of complete multipartite graphs with at most three parts, wheels, fans, paths, cycles and trees of radius two, characterise the graphs $G$ with $GC(G)=|V(G)|$ in terms of antitwins, relate global coalitions to perfect coalitions, and study unicyclic graphs of radius at most two. Finally, we interpret $gc$-partitions in the language of fair division of indivisible goods and pose several open problems.\\ \textbf{2020 Mathematics Subject Classification:} 05C69, 91B32.\\ \textbf{JEL Classification:} C72, C78, D63.\\ \textbf{Keywords}: Global domination, coalition, global coalition partition, antitwins, trees, unicyclic graphs, fair division.

arXiv comment32 pages