2025/07/24 by Boštjan Brešar, Brešar, Boštjan, Michael A. Henning +3 · 1 citation
Economics, Econometrics and Finance · Computer Science · #Game Theory and Voting Systems #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2507.18306
Given a graph G=(V(G),E(G)), a set S⊆ V(G) is called a k-dominating set if every vertex in V(G)∖ S has at least k neighbors in S. Two disjoint sets A,B⊂ V(G) form a k-coalition in G if neither set is a k-dominating set in G but their union A∪ B is a k-dominating set. A partition Ω of V(G) is a k-coalition partition if each set in Ω is either a k-dominating set of cardinality k or forms a k-coalition with another set in Ω. The k-coalition number Ck(G) equals the maximum cardinality of a k-coalition partition of G. In this work, we give general upper and lower bounds on this parameter. In particular, we show that if G has minimum degree δ≥ 2 and maximum degree Δ≥ 4 \lfloor δ/2 \rfloor, then C2(G) ≤ (Δ-2\lfloor δ/2 \rfloor+1)(\lfloor δ/2 \rfloor+1) + \lceil δ/2 \rceil+1, and this bound is sharp. If T is a tree of order~n ≥ 2, then we prove the upper bound C2(T) ≤ \lfloor (n)/(2)\rfloor+1 and we characterize the extremal trees achieving equality in this bound. We determine the exact value of Ck(G) for any cubic graph G and k≥2. Finally, we give the exact value of Ck for any complete bipartite graph, which completes a partial result and resolves an issue from an earlier paper.