TY - JOUR

T1 - On independent coalition in graphs and independent coalition graphs

AU - Alikhani, Saeid

AU - Bakhshesh, Davood

AU - Golmohammadi, Hamidreza

AU - Klavžar, Sandi

N1 - The work of Hamidreza Golmohammadi was supported by the Russian Science Foundation under the grant no. 23-21-00459. The work of Sandi Klavˇzar was supported by the Slovenian Research Agency (ARIS) under the grants P1-0297, J1-2452, and N1-0285.

PY - 2025

Y1 - 2025

N2 - An independent coalition in a graph G consists of two disjoint, independent vertex sets V1 and V2, such that neither V1 nor V2 is a dominating set, but the union V1∪V2 is an independent dominating set of G. An independent coalition partition of G is a partition {V1,...,Vk} of V (G) such that for every i∈[k], either the set Vi consists of a single dominating vertex of G, or Vi forms an independent coalition with some other part Vj. The independent coalition number IC (G) of G is the maximum order of an independent coalition of G. The independent coalition graph ICG (G, π) of π = {V1,...,Vk} (and of G) has the vertex set {V1,...,Vk}, vertices Vi and Vj being adjacent if Vi and Vj 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) ∈ {n(G),n(G) - 1} are characterized. Some properties of ICG(G,π) are presented. The independent coalition graphs of paths are characterized, and the independent coalition graphs of cycles described.

AB - An independent coalition in a graph G consists of two disjoint, independent vertex sets V1 and V2, such that neither V1 nor V2 is a dominating set, but the union V1∪V2 is an independent dominating set of G. An independent coalition partition of G is a partition {V1,...,Vk} of V (G) such that for every i∈[k], either the set Vi consists of a single dominating vertex of G, or Vi forms an independent coalition with some other part Vj. The independent coalition number IC (G) of G is the maximum order of an independent coalition of G. The independent coalition graph ICG (G, π) of π = {V1,...,Vk} (and of G) has the vertex set {V1,...,Vk}, vertices Vi and Vj being adjacent if Vi and Vj 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) ∈ {n(G),n(G) - 1} are characterized. Some properties of ICG(G,π) are presented. The independent coalition graphs of paths are characterized, and the independent coalition graphs of cycles described.

KW - dominating set

KW - independent coalition

KW - independent coalition graph

KW - independent coalition number

KW - independent set

UR - https://www.mendeley.com/catalogue/e44c6d1f-2e9a-307c-b3ff-aa00ec63ed8a/

U2 - 10.7151/dmgt.2543

DO - 10.7151/dmgt.2543

M3 - Article

VL - 45

SP - 533

EP - 544

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

SN - 1234-3099

IS - 2

ER -