Journal of the Iranian Mathematical Society

Journal of the Iranian Mathematical Society

Fair coalition in graphs

Document Type : Research Article

Authors
Saeid Alikhani
Abbas Jafari
Maryam Safazadeh
Department of Mathematical Sciences, Yazd University, Yazd, Iran.
10.30504/jims.2025.538329.1273
Abstract
Let $G=(V,E)$ be a simple graph‎. ‎A dominating set of $G$ is a subset $D\subseteq 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 $\gamma(G)$‎, ‎is the domination number of $G$‎. ‎For $k \geq 1$‎, ‎a $k$-fair dominating set ($kFD$-set) in $G$‎, ‎is a dominating set $S$ such that $|N(v) \cap D|=k$ for every vertex $ v \in V\setminus D$‎. ‎A fair dominating set in $G$ is a $kFD$-set for some integer $k\geq 1$‎. ‎We consider $1FD$-sets and define a fair coalition in a graph $G$ as a pair of disjoint subsets $A_1‎, ‎A_2 \subseteq A$ that satisfy the following conditions‎: ‎(a) neither $A_1$ nor $A_2$ constitutes a $1$-fair dominating set of $G$‎, ‎and (b) $A_1\cup A_2$ constitutes a $1$-fair dominating set of $G$.‎ ‎ A fair coalition partition of a graph $G$ is a partition $\Upsilon = \{A_1,A_2,\ldots,A_k\}$ of its vertex set‎ ‎ such that every set $A_i$ of $\Upsilon$ 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 $A_j\in \Upsilon$‎. ‎ We define the fair coalition number of $G$ as the maximum cardinality of a fair coalition partition of $G$‎, ‎and we denote it by $\mathcal{C}_f(G)$‎.‎ We initiate the study of the fair coalition in graphs and obtain $\mathcal{C}_f(G)$ for some specific graphs‎.
Keywords
Fair domination
fair coalition
cubic graphs
Petersen graph
cycle
Subjects
[1] S. Alikhani, H. R. Golmohammadi and E. V. Konstantinova, Coalition of cubic graphs of order at most 10, Commun. Comb. Optim. 9 (2024), no. 3, 437–450.
[2] S. Alikhani, D. Bakhshesh and H. Golmohammadi, Total coalitions in graphs, Quaest. Math. 47 (2024), no. 11, 2283–2294.
[3] S. Alikhani, D. Bakhshesh, H. Golmohammadi and E. V. Konstantinova, Connected coalitions in graphs, Discuss. Math. Graph Theory 44 (2024), no. 4, 1551–1566.
[4] S. Alikhani and M. Safazadeh, Fair dominating sets of paths, J. Inform. Optim. Sci. 44 (2023), no. 5, 855–864.
[5] S. Alikhani and M. Safazadeh, On the number of fair dominating sets of graphs, Adv. Stud. Euro-Tbil. Math. J. 16 (2023), suppl. 1, 59–69.
[6] D. Bakhshesh, M. A. Henning and D. Pradhan, On the coalition number of trees, Bull. Malays. Math. Sci. Soc. 46 (2023), no. 3, paper no. 95, 18 pp.
[7] Y. Caro, A. Hansberg and M. Henning, Fair domination in graphs, Discrete Math. 312 (2012), no. 19, 2905–2914.
[8] E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks, 7 (1977), no. 3, 247–261.
[9] H. R. Golmohammadi, Total coalitions of cubic graphs of order at most 10, Comm. Combin. Optim. 10 (2025), no. 3, 601–615.
[10] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae and R. Mohan, Introduction to coalitions in graphs, AKCE Int. J. Graphs Comb. 17 (2020), no. 2, 653–659.
[11] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Coalition graphs, Commun. Comb. Optim. 8 (2023), no. 2, 423–430.
[12] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae and R. Mohan, Coalition graphs of paths, cycles, and trees, Discuss. Math. Graph Theory 43 (2023), no. 4, 931–946.
[13] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae and R. Mohan, Upper bounds on the coalition number, Australas. J. Combin. 80 (2021) 442–453.
[14] A. Jafari, S. Alikhani and D. Bakhshesh, k-coalitions in graphs, Australas. J. Combin. 92 (2025) 194–209.
[15] D. A. Mojdeh and I. Masoumi, Edge coalitions in graphs, Available at https://arxiv.org/abs/2302.10926.
[16] D. A. Mojdeh and M. R. Samadzadeh, Perfect coalition in graphs, Available at https://arxiv.org/pdf/2409.10185.
 
Journal of the Iranian Mathematical Society
Volume 6, Issue 2
August 2025
Pages 133-147