آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 122 |
| تعداد مقالات | 1,538 |
| تعداد مشاهده مقاله | 1,628,301 |
| تعداد دریافت فایل اصل مقاله | 1,525,832 |
On coalition graphs and coalition count of graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 10 خرداد 1405 اصل مقاله (370.59 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.31056.2728 | ||
| نویسندگان | ||
| Swathi Shetty؛ Sayinath Udupa N V* ؛ Rakshith B R | ||
| Manipal Institute of Technology, Manipal Academy of Higher Education, Manipal, India | ||
| چکیده | ||
| Let $G$ be graph with vertex set $V(G)$ and order $n$. A set $S \subseteq V(G)$ is a dominating set of a graph $G$ if every vertex in $V(G) \backslash S$ is adjacent to at least one vertex in $S$. A coalition in a graph $G$ consists of two disjoint sets of vertices $V_1$ and $V_2$, neither of which is a dominating set but whose union $V_1 \cup V_2$ is a dominating set. A coalition partition, abbreviated $c$-partition, in a graph $G$ is a vertex partition $\pi=\left\{V_1 , V_2,\dots, V_k\right\}$ such that every set $V_i$ of $\pi$ is either a singleton dominating set, or is not a dominating set but forms a coalition with another set $V_j$ in $\pi$. The sets $V_i$ and $V_j$ are coalition partners in $G$. The coalition number $C(G)$ equals the maximum order $k$ of a $c$-partition of $G$. For any graph $G$ with a $c$-partition $\pi=\left\{V_1,V_2,\dots,V_k\right\}$, the coalition graph $CG(G,\pi)$ of $G$ is a graph with vertex set $V_1,V_2,\dots, V_k$, corresponding one-to-one with the set $\pi$, and two vertices $V_i$ and $V_j$ are adjacent in $CG(G,\pi)$ if and only if the sets $V_i$ and $V_j$ are coalition partners in $\pi$. In [T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R. Mohan, Coalition graphs, Commun. Comb. Optim. 8 (2023), 423-430], authors proved that for every graph $G$ there exist a graph $H$ and $c$-partition $\pi$ such that $CG(H,\pi)\cong G$, and raised the question: Does there exist a graph $H^*$ of smaller order $n^*$ and size $m^*$ with a $c$-partition $\pi^*$ such that $CG(H^*,\pi^*)\cong G$? In this paper, we constructed a graph $H^*$ of small order and size and a $c$-partition $\pi^*$ such that $CG(H^*,\pi^*)\cong G$. Recently, Haynes et al. [Introduction to coalitions in graphs, AKCE Int. J. Graphs Comb. 17 (2020), 653-659] defined the coalition count $c(G)$ of a graph $G$ as the maximum number of different coalition in any $c$-partition of $G$. We characterize all graphs $G$ with $c(G)=1$. Further, imposing some suitable conditions on coalition number, we study the properties of coalition count of graph. | ||
| کلیدواژهها | ||
| Dominating set؛ Coalition partition؛ Coalition number | ||
| مراجع | ||
|
[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ˇzar, On independent coalition in graphs and independent coalition graphs, Discuss. Math. Graph Theory 45 (2025), no. 2, 533–544. http://dx.doi.org/10.7151/dmgt.2543
3] D. Bakhshesh, M.A. Henning, and D. Pradhan, On the coalition number of trees, Bull. Malays. Math. Sci. Soc. 46 (2023), no. 3, 95. https://doi.org/10.1007/s40840-023-01492-4
[4] 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. https://doi.org/10.1080/09728600.2020.1832874
[5] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R. Mohan, Upper bounds on the coalition number, Austral. J. Combin. 80 (2021), no. 3, 442–453.
[6] 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. https://doi.org/10.22049/cco.2022.27916.1394
[7] 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. https://doi.org/10.7151/dmgt.2416
[8] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Topics in Domination in Graphs, Springer, 2020.
[9] T.W. Haynes, S.T. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, CRC press, 2013.
[10] M.A. Henning and D.A. Mojdeh, Double coalitions in graphs, Bull. Malays. Math. Sci. Soc. 48 (2025), no. 2, 51. https://doi.org/10.1007/s40840-025-01831-7 [11] M.R. Samadzadeh, D.A. Mojdeh, and R. Nadimi, Paired coalition in graphs, AKCE Int. J. Graphs Comb. 22 (2025), no. 1, 43–54. https://doi.org/10.1080/09728600.2024.2389070
[12] F. Yang, Q. Sun, and C. Zhang, Characterizations of graphs with equal vertex and coalition number, Discrete Appl. Math. 381 (2026), 112–119. https://doi.org/10.1016/j.dam.2025.11.002
[13] B. Zelinka, On domatic numbers of graphs, Math. Slovaca 31 (1981), no. 1, 91–95.
[14] B. Zelinka, Domatic number and degrees of vertices of a graph, Math. Slovaca 33 (1983), no. 2, 145–147. | ||
|
آمار تعداد مشاهده مقاله: 9 تعداد دریافت فایل اصل مقاله: 10 |
||