Paired coalition in graphs

Abstract

A paired coalition in a graph [Formula: see text] consists of two disjoint sets of vertices [Formula: see text] and [Formula: see text], neither of which is a paired dominating set but whose union [Formula: see text] is a paired dominating set. A paired coalition partition (abbreviated pc-partition) in a graph G is a vertex partition [Formula: see text] such that each set [Formula: see text] of [Formula: see text] is not a paired dominating set but forms a paired coalition with another set [Formula: see text]. The paired coalition graph [Formula: see text] of the graph G with the pc-partition [Formula: see text] of G, is the graph whose vertices correspond to the sets of [Formula: see text], and two vertices [Formula: see text] and [Formula: see text] are adjacent in [Formula: see text] if and only if their corresponding sets [Formula: see text] and [Formula: see text] form a paired coalition in G. In this paper, we initiate the study of paired coalition partitions and paired coalition graphs. In particular, we determine the paired coalition number of paths and cycles, obtain some results on paired coalition partitions in trees and characterize pair coalition graphs of paths, cycles and trees. We also characterize triangle-free graphs G of order n with [Formula: see text] and unicyclic graphs G of order n with [Formula: see text].

Keywords

• Paired coalition
• paired coalition partition
• paired dominating set
• paired coalition graph
• 05C69