آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 125 |
| تعداد مقالات | 1,585 |
| تعداد مشاهده مقاله | 1,755,044 |
| تعداد دریافت فایل اصل مقاله | 1,636,614 |
Roman Coalition Partitions in Graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 01 اردیبهشت 1405 اصل مقاله (423.34 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.30582.2542 | ||
| نویسندگان | ||
| Juan Carlos Valenzuela Tripodoro* 1؛ Mustapha Chellali2؛ Hamidreza Golmohammadi3 | ||
| 1Department of Mathematics, University of C´adiz, Spain | ||
| 2LAMDA-RO Laboratory, Dept. of Mathematics, Univ. of Blida, Blida, Algeria | ||
| 3Sobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk, 630090, Russia 2) Sobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk, 630090, Russia | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Coalition؛ Roman coalition؛ Roman dominating set؛ Roman coalition partition | ||
| مراجع | ||
|
[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 | ||
|
آمار تعداد مشاهده مقاله: 133 تعداد دریافت فایل اصل مقاله: 80 |
||