2023/06/03 by Mohammad Reza Samadzadeh, Doost Ali Mojdeh, Samadzadeh, Mohammad Reza +1 · 1 citation
Computer Science · #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2306.02079
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 π= \lbrace V1,V2,… ,Vk \rbrace 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.