2025/07/20 by Saeid Alikhani, Abbas Jafari, Alikhani, Saeid +3
Computer Science · Economics, Econometrics and Finance · #05C25 #05C60 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2507.15080
openalex publication_date 2025/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V,E) be a simple graph. A dominating set of G is a subset D⊆ V such that every vertex not in D is adjacent to at least one vertex in D. The cardinality of a smallest dominating set of G, denoted by γ(G), is the domination number of G. For k ≥ 1, a k-fair dominating set (kFD-set) in G, is a dominating set S such that |N(v) ∩ D|=k for every vertex v ∈ V∖ D. A fair dominating set in G is a kFD-set for some integer k≥ 1. We consider 1FD-sets and define a fair coalition in a graph G as a pair of disjoint subsets A1, A2 ⊆ A that satisfy the following conditions: (a) neither A1 nor A2 constitutes a 1-fair dominating set of G, and (b) A1∪ A2 constitutes a 1-fair dominating set of G. A fair coalition partition of a graph G is a partition Υ= \A1,A2,…,Ak\ of its vertex set such that every set Ai of Υ is either a singleton 1-fair dominating set of G, or is not a 1-fair dominating set of G but forms a fair coalition with another non-1-fair dominating set Aj∈ Υ. We define the fair coalition number of G as the maximum cardinality of a fair coalition partition of G, and we denote it by Cf(G). We initiate the study of the fair coalition in graphs and obtain Cf(G) for some specific graphs.