2026/07/15 by Saeid Alikhani, Nima Ghanbari
#math.CO
We introduce and investigate the structural properties of super coalition partitions in graphs, a novel direction that bridges cooperative resource deployment with rigid domination criteria. Based on the foundational concept of super domination, a super coalition partition is defined as a vertex set partitioning Υ= \A1, A2, …, Ak\ such that no single class Ai constitutes a valid super dominating set, yet every class can be paired with at least one distinct partner class Aj to form a union Ai ∪ Aj that achieves full super domination over the graph. The super coalition number, denoted by Cs(G), represents the maximum possible cardinality of such a partition. In this paper, we establish general operational bounds for Cs(G) using the underlying order and the super domination number γsp(G), demonstrate its relation to the super domatic number dsp(G), analyze its computational complexity proving its NP-complete nature under general conditions, and provide exact determinations for key standard graph architectures including paths, cycles, complete graphs, stars, wheels, and friendship configurations. We conclude by proving that the super coalition number can grow arbitrarily large.