Connected coalitions in graphs

The connected coalition in a graph \(G=(V,E)\) consists of two disjoint sets of vertices \(V_{1}\) and \(V_{2}\), neither of which is a connected dominating set but whose union \(V_{1}\cup V_{2}\), is a connected dominating set. A connected coalition partition in a graph \(G\) of order \(n=|V|\) is...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-02
Main Authors: Alikhani, Saeid, Bakhshesh, Davood, Golmohammadi, Hamidreza, Konstantinova, Elena V
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Graph theory
Graphs
Partitions (mathematics)
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The connected coalition in a graph \(G=(V,E)\) consists of two disjoint sets of vertices \(V_{1}\) and \(V_{2}\), neither of which is a connected dominating set but whose union \(V_{1}\cup V_{2}\), is a connected dominating set. A connected coalition partition in a graph \(G\) of order \(n=|V|\) is a vertex partition \(\psi\) = \(\{V_1, V_2,..., V_k \}\) such that every set \(V_i \in \psi\) either is a connected dominating set consisting of a single vertex of degree \(n-1\), or is not a connected dominating set but forms a connected coalition with another set \(V_j\in \psi\) which is not a connected dominating set. The connected coalition number, denoted by \(CC(G)\), is the maximum cardinality of a connected coalition partition of \(G\). In this paper, we initiate the study of connected coalition in graphs and present some basic results. Precisely, we characterize all graphs that have a connected coalition partition. Moreover, we show that for any graph \(G\) of order \(n\) with \(\delta(G)=1\) and with no full vertex, it holds that \(CC(G)
ISSN:2331-8422