چکیده
|
A paired coalition in a graph G=(V,E) consists of two disjoint sets of vertices V1 and V2 , neither of which is a paired dominating set but whose union V1∪V2 is a paired dominating set. A paired coalition partition (abbreviated pc-partition) in a graph G is a vertex partition π={V1,V2,…,Vk} such that each set Vi of π is not a paired dominating set but forms a paired coalition with another set Vj∈π . The paired coalition graph PCG(G,π) of the graph G with the pc-partition π of G, is the graph whose vertices correspond to the sets of π , and two vertices Vi and Vj are adjacent in PCG(G,π) if and only if their corresponding sets Vi and Vj 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 PC(G)=n and unicyclic graphs G of order n with PC(G)=n−2 .
|