Perfect coalition in graphs

Abstract

A perfect dominating set in a graph G = (V, E) is a subset S ⊆ V such that each vertex in V \ S has exactly one neighbor in S. A perfect coalition in G consists of two disjoint sets of vertices V₁ and V₂ such that i) neither V₁ nor V₂ is a dominating set, ii) each vertex in V(G) \ V₁ has at most one neighbor in V₁ and each vertex in V(G) \ V₂ has at most one neighbor in V₂, and iii) V₁ ∪ V₂ is a perfect dominating set. A perfect coalition partition (abbreviated prc-partition) in a graph G is a vertex partition π = {V₁, V₂, …, V_k} such that for each set V_i of π, either V_i is a singleton dominating set or there exists a set V_j ∈ π that forms a perfect coalition with V_i. In this paper, we initiate the study of perfect coalition partitions in graphs. We obtain a bound on the number of perfect coalitions involving each member of a perfect coalition partition, in terms of maximum degree. The perfect coalition of some special graphs are investigated. Graphs with minimum degree one, triangle-free graphs and trees with large perfect coalition numbers are investigated.