Independent coalition in graphs: existence and characterization

Mohammad Reza Samadzadeh; Doost Ali Mojdeh

paper

Independent coalition in graphs: existence and characterization

arXiv:2306.02079

Abstract

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, $i c$ -partition, in a graph $G$ is a vertex partition $I ¨ = {V_{1}, V_{2}, \dots, V_{k}}$ such that each set $V_{i}$ of $I ¨ $ either is a singleton dominating set, or is not an independent dominating set but forms an independent coalition with another set $V_{j} \in I ¨ $ . The maximum number of classes of an $i c$ -partition of $G$ is the independent coalition number of $G$ , denoted by $I C (G)$ . In this paper we study the concept of $i c$ -partition. In particular, we discuss the possibility of the existence of $i c$ -partitions in graphs and introduce a family of graphs for which no $i c$ -partition exists. We also determine the independent coalition number of some classes of graphs and investigate graphs $G$ of order $n$ with $I C (G) \in {1, 2, 3, 4, n}$ and the trees $T$ of order $n$ with $I C (T) = n - 1$ .

17 pages