Perfect coalition in graphs
Doost Ali Mojdeh, Mohammad Reza Samadzadeh · Electronic Journal of Graph Theory and Applications · 2025
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 1 and V 2 such that i) neither V 1 nor V 2 is a dominating set, ii) each vertex in V(G) \ V 1 has at most one neighbor in V 1 and each vertex in V(G) \ V 2 has at most one neighbor in V 2 , and iii) V 1 ∪ V 2 is a perfect dominating set. A perfect coalition partition (abbreviated prc -partition) in a graph G is a vertex partition π = {V 1 , V 2 , …, 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.