2024/07/12 by Jafari, Abbas, Alikhani, Saeid, Bakhshesh, Davood · 2 citations
#05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2407.09332
In this paper, we propose and investigate the concept of k-coalitions in graphs, where k≥ 1 is an integer. A k-coalition refers to a pair of disjoint vertex sets that jointly constitute a k-dominating set of the graph, meaning that every vertex not in the set has at least k neighbors in the set. We define a k-coalition partition of a graph as a vertex partition in which each set is either a k-dominating set with exactly k members or forms a k-coalition with another set in the partition. The maximum number of sets in a k-coalition partition is called the k-coalition number of the graph represented by Ck(G). We present fundamental findings regarding the properties of k-coalitions and their connections with other graph parameters. We obtain the exact values of 2-coalition number of some specific graphs and also study graphs with large 2-coalition number.