Independent coalition in graphs: existence and characterization
Mohammad Reza Samadzadeh, Doost Ali Mojdeh · Ars Mathematica Contemporanea · 2024
An independent coalition in a graph G consists of two disjoint sets of vertices V1 and V2 neither of which is an independent dominating set but whose union V1 ∪ V2 is an independent dominating set. An independent coalition partition, abbreviated, ic-partition, in a graph G is a vertex partition π = {V1, V2, …, Vk} such that each set Vi of π either is a singleton dominating set, or is not an independent dominating set but forms an independent coalition with another set Vj ∈ π. The maximum number of classes of an ic-partition of G is the independent coalition number of G, denoted by IC(G). In this paper we study the concept of ic-partition. In particular, we discuss the possibility of the existence of ic-partitions in graphs and introduce a family of graphs for which no ic-partition exists. We also determine the independent coalition number of some classes of graphs and investigate graphs G of order n with IC(G) ∈ {1, 2, 3, 4, n} and the trees T of order n with IC(T) = n − 1.