Independent coalition in graphs: existence and characterization

• Published in: arXiv.org 2024-07
• Main Authors: Samadzadeh, Mohammad Reza, Doost Ali Mojdeh
• Format: Article
• Language: English
• Subjects: Apexes; Graph theory; Graphs; Partitions (mathematics); Trees (mathematics)
• ISSN: 2331-8422

An independent coalition in a graph \(G\) consists of two disjoint sets of vertices \(V_1\) and \(V_2\) neither of which is an independent dominating set but whose union \(V_1 \cup V_2\) is an independent dominating set. An independent coalition partition, abbreviated, \(ic\)-partition, in a graph \(G\) is a vertex partition \(\pi= \lbrace V_1,V_2,\dots ,V_k \rbrace\) such that each set \(V_i\) of \(\pi\) either is a singleton dominating set, or is not an independent dominating set but forms an independent coalition with another set \(V_j \in \pi\). 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)\in\{1,2,3,4,n\}\) and the trees \(T\) of order \(n\) with \(IC(T)=n-1\).