Perfect coalition in graphs - Mojdeh, Doost Ali; Samadzadeh, Mohammad Reza (Electronic Journal of Graph Theory and Applications (EJGTA), 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 V1 and V2 such that i) neither V1 nor V2 is a dominating set, ii) each vertex in V(G) \ V1 has at most one neighbor in V1 and each vertex in V(G) \ V2 has at most one neighbor in V2, and iii) V1 ∪ V2 is a perfect dominating set. A perfect coalition partition (abbreviated prc-partition) in a graph G is a vertex partition π = {V1, V2, …, Vk} such that for each set Vi of π, either Vi is a singleton dominating set or there exists a set Vj ∈ π that forms a perfect coalition with Vi. 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.