Roman Coalition Partitions in Graphs

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, University of C´adiz, Spain

2 LAMDA-RO Laboratory, Dept. of Mathematics, Univ. of Blida, Blida, Algeria

3 Sobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk, 630090, Russia 2) Sobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk, 630090, Russia

Abstract

The Roman domination problem is a combinatorial optimization problem on a graph asking to assign a label from $\{0,1,2\}$ to each vertex feasibly, such that the total sum of assigned labels is minimized. Let $G=(V,E)$ be a graph, and let \(U_1, U_2\subseteq V\) be two non-empty disjoint subsets. We say that the pair \( \{U_1,U_2\}\) is Roman-feasible if there exists a Roman dominating function \(f:V\to \{0,1,2\}\) such that \(V_0=V\setminus (U_1\cup U_2),\) \(V_1=U_i\) and \(V_2=U_{3-i}\) for some \(i\in \{1,2\},\) where $V_j$ denotes the set of vertices assigned label $j$ by $f$. The set \(\{U_1,U_2,U_3\}\) is a Roman coalition if the following two conditions hold: (i) the pair \(\{U_i,U_j\}\) is not Roman-feasible for any different \(1\le i,j\le 3;\) (ii) there exists \(k\) such that the pair \(\{U_i\cup U_j, U_k\}\) is Roman-feasible, where \(\{i,j,k\}=\{1,2,3\}.\) The purpose of this paper is to introduce and study the new concept of Roman coalitions in graphs, providing basic properties, lower and upper bounds, as well as exact values in specific cases.

Keywords

Main Subjects

References

[1] S. Alikhani, D. Bakhshesh, and H. Golmohammadi, Total coalitions in graphs, Quaest. Math. 47 (2024), no. 11, 2283–2294. https://doi.org/10.2989/16073606.2024.2365365
[2] S. Alikhani, D. Bakhshesh, H. Golmohammadi, and S. Klavžar, On independent coalition in graphs and independent coalition graphs, Discuss. Math. Graph Theory 45 (2025), no. 2, 533–544. https://doi.org/10.7151/dmgt.2543
[3] S. Alikhani, D. Bakhshesh, H. Golmohammadi, and E.V. Konstantinova, Connected coalitions in graphs, Discuss. Math. Graph Theory 44, 1551–1566. https://doi.org/10.7151/dmgt.2509
[4] D. Bakhshesh, M.A. Henning, and D. Pradhan, On the coalition number of trees, Bull. Malays. Math. Sci. Soc. 46 (2023), no. 3, Article number: 95. https://doi.org/10.1007/s40840-023-01492-4
[5] J. Barát and Z.L. Blázsik, General sharp upper bounds on the total coalition number, Discuss. Math. Graph Theory 44 (2024), no. 1567-1584. https://doi.org/10.7151/dmgt.2511
[6] B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979), no. 3, 241–249. https://doi.org/10.1002/jgt.3190030306
[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, Topics in Domination in Graphs, vol. 64, Springer, 2020, pp. 365–409. https://doi.org/10.1007/978-3-030-51117-3-11
[8] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, Structures of domination in graphs, vol. 66, Springer, 2021, pp. 273–307. https://doi.org/10.1007/978-3-030-58892-2-10
[9] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22. https://doi.org/10.1016/j.disc.2003.06.004
[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 Combin. 17 (2020), no. 2, 653–659. https://doi.org/10.1080/09728600.2020.1832874
[11] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, Upper bounds on the coalition number, Australas. J. Combin. 80 (2021), no. 3, 442–453.
[12] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, Coalition graphs, Commun. Comb. Optim. 8 (2023), no. 2, 423–430. https://doi.org/10.22049/cco.2022.27916.1394
[13] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, Coalition graphs of paths, cycles, and trees, Discuss. Math. Graph Theory 43 (2023), no. 4, 931–946. https://doi.org/10.7151/dmgt.2416
[14] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, Self-coalition graphs, Opuscula Math. 43 (2023), no. 2, 173–183. https://doi.org/10.7494/opmath.2023.43.2.173
[15] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of domination in graphs, CRC press, 1998.
[16] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in graphs: Core concepts, Springer, 2023.
[17] M.A. Henning and S.N. Jogan, A characterization of graphs with given total coalition numbers, Discrete Appl. Math. 358 (2024), 395–403. https://doi.org/10.1016/j.dam.2024.07.031
[18] S.M. Sheikholeslami and L. Volkmann, The Roman domatic number of a graph, Appl. Math. Lett. 23 (2010), no. 10, 1295–1300. https://doi.org/10.1016/j.aml.2010.06.016
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 21 April 2026

Files

Share

How to cite

Statistics