Perfect coalition in graphs - Mojdeh, Doost Ali; Samadzadeh, Mohammad Reza (GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB, 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.