2024/04/17 by Golmohammadi, Hamidreza, Alikhani, Saeid, Ghanbari, Nima +2
#05C60 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2404.11575
For a graph G=(V,E), a set D⊂ V(G) is a strong dominating set of G, if for every vertex x∈ V (G)∖ D there is a vertex y∈ D with xy ∈ E(G) and deg(x)≤ deg(y). A strong coalition consists of two disjoint sets of vertices V1 and V2, neither of which is a strong dominating set but whose union V1∪ V2, is a strong dominating set. A vertex partition Ω=\V1, V2,..., Vk \ of vertices in G is a strong coalition partition, if every set Vi ∈Ω either is a strong dominating set consisting of a single vertex of degree n-1, or is not a strong dominating set but produces a strong coalition with another set Vj ∈ Ω that is not a strong dominating set. The maximum cardinality of a strong coalition partition of G is the strong coalition number of G and is denoted by SC(G). In this paper, we study properties of strong coalitions in graphs.