2025/02/11 by Boštjan Brešar, Brešar, Boštjan, Sandi Klavžar +3 · 1 citation
Economics, Econometrics and Finance · #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2502.07310
openalex publication_date 2025/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V(G),E(G)) be a graph with minimum degree k. A subset S⊆ V(G) is called a total k-dominating set if every vertex in G has at least k neighbors in S. Two disjoint sets A,B⊂ V(G) form a total k-coalition in G if none of them is a total k-dominating set in G but their union A∪ B is a total k-dominating set. A vertex partition Ω=\V1,…,V|Ω|\ of G is a total k-coalition partition if each set Vi forms a total k-coalition with another set Vj. The total k-coalition number \rm TCk(G) of G equals the maximum cardinality of a total k-coalition partition of G. In this paper, the above-mentioned concept are investigated from combinatorial points of view. Several sharp lower and upper bounds on \rm TCk(G) are proved, where the main emphasis is given on the invariant when k=2. As a consequence, the exact values of \rm TC2(G) when G is a cubic graph or a 4-regular graph are obtained. By using similar methods, an open question posed by Henning and Mojdeh regarding double coalition is answered. Moreover, \rm TC3(G) is determined when G is a cubic graph.