Abstract: Two sets of vertices of a graph $G$ form a coalition if none of them is dominating but their union is a dominating set of $G$. A coalition partition is a vertex partition of $G$ such that every subset of the partition is not dominating but form a coalition with some other subset. The coalition number $C(G)$ is the maximal number of subsets in the coalition partition of $G$. For every $D \ge 2$, we present series of graphs $G$ with the maximal degree $D$ that have maximal $C(G)$ and minimal number of vertices. Moreover, we construct series of graphs $G$ with the maximal degree $D$ that have maximal number of coalitions. The similar examples of $D$-regular graphs $G$ are also presented. The problem is solved for the cases of conncted and disconnected graphs $G$.1

Cite: Glebov A.
Extremal graphs for the coalition domination problem
XXIV International conference “Mathematical Optimization Theory and Operations Research” 07-11 Jul 2025