Independent coalition in graphs: existence and characterization

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 \...

Full description

Saved in:
Bibliographic Details
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)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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\).
ISSN:2331-8422