DMGT

An independent coalition in a graph $G$ consists of two disjoint, independent vertex sets $V_1$ and $V_2$, such that neither $V_1$ nor $V_2$ is a dominating set, but the union $V_1\cup V_2$ is an independent dominating set of $G$. An independent coalition partition of $G$ is a partition $\{V_1, \ldots, V_k\}$ of $V(G)$ such that for every $i\in [k]$, either the set $V_i$ consists of a single dominating vertex of $G$, or $V_i$ forms an independent coalition with some other part $V_j$. The independent coalition number $IC(G)$ of $G$ is the maximum order of an independent coalition of $G$. The independent coalition graph $\textrm{ICG}(G,\pi)$ of $\pi=\{V_1, \ldots, V_k\}$ (and of $G$) has the vertex set $\{V_1,\ldots, V_k\}$, vertices $V_i$ and $V_j$ being adjacent if $V_i$ and $V_j$ form an independent coalition in $G$. In this paper, a large family of graphs with $IC(G) = 0$ is described and graphs $G$ with $IC(G)\in \{n(G), n(G)-1\}$ are characterized. Some properties of $\textrm{ICG}(G,\pi)$ are presented. The independent coalition graphs of paths are characterized, and the independent coalition graphs of cycles described.

Keywords:

dominating set, independent set, independent coalition, independent coalition number, independent coalition graph

References:

S. Alikhani, D. Bakhshesh and H. Golmohammadi, Introduction to total coalitions in graphs (2022).
arXiv: 2211.11590v2
S. Alikhani, D. Bakhshesh, H.R. Golmohammadi and E.V. Konstantinova, Connected coalitions in graphs, Discuss. Math. Graph Theory 44 (2024) 1551–1566.
https://doi.org/10.7151/dmgt.2509
S. Alikhani, H.R. Golmohammadi and E.V. Konstantinova, Coalition of cubic graphs of order at most $10$, Commun. Comb. Optim. 9 (2024) 437–450.
https://doi.org/10.22049/cco.2023.28328.1507
D. Bakhshesh, M.A. Henning and D. Pradhan, On the coalition number of trees, Bull. Malays. Math. Sci. Soc. 46 (2023) 95.
https://doi.org/10.1007/s40840-023-01492-4
J. Barát and Z.L. Blázsik, General sharp upper bounds on the total coalition number, Discuss. Math. Graph Theory 44 (2024) 1567–1584.
https://doi.org/10.7151/dmgt.2511
E.J. Cockayne and S.T. Hedetniemi, Disjoint independent dominating sets in graphs, Discrete Math. 15 (1976) 213–222.
https://doi.org/10.1016/0012-365X(76)90026-1
J.E. Dunbar, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisely, R.C. Laskar and D.F. Rall, Fall colorings of graphs, J. Combin. Math. Combin. Comput. 33 (2000) 257–273.
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) 653–659.
https://doi.org/10.1080/09728600.2020.1832874
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.
T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Self-coalition graphs, Opuscula Math. 43 (2023) 173–183.
https://doi.org/10.7494/opmath.2023.43.2.173
T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Coalition graphs, Commun. Comb. Optim. 8 (2023) 423–430.
https://doi.org/10.22049/CCO.2022.27916.1394
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) 931–946.
https://doi.org/10.7151/dmgt.2416
T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Domination in Graphs: Core Concepts, Springer Monogr. Math. (Springer, Cham, 2023).
https://doi.org/10.1007/978-3-031-09496-5
H. Kaul and C. Mitillos, On graph fall-coloring: Existence and constructions, Graphs Combin. 35 (2019) 1633–1646.
https://doi.org/10.1007/s00373-019-02082-7
M.R. Samadzadeh and D.A. Mojdeh, Independent coalition in graphs: existence and characterization, Ars Math. Contemp. 24 (2024) #P3.09.
https://doi.org/10.26493/1855-3974.3113.6f7