On the perfect differential and perfect Roman domination in complementary prisms

Faculty of Science, Department of Computer Science, Dokuz Eylul University, 35160 Izmir, Turkey

^* Corresponding author: zeynep.berberler@deu.edu.tr; odabaszeynep@gmail.com

Received: 8 September 2023
Accepted: 27 March 2025

Abstract

Let G = (V, E) be a graph of order n. For S ⊆ V (G), the set N_p(S) is defined as the perfect neighborhood of S such that all vertices in V (G)∖S have exactly one neighbor in S. The perfect differential of S is defined to be ∂_p(S) = |N_p(S)| − |S| and the perfect differential of a graph is defined as ∂_p(G) = max{∂_p(S) : S ⊆ V (G)}. A perfect Roman dominating function is defined as a Roman dominating function f satisfying the condition that every vertex u for which f(u) = 0 is adjacent to exactly one vertex v for which f(v) = 2. The perfect Roman domination number, denoted by γ^p_R(G), is the minimum weight among all perfect Roman dominating functions on G, that is γ^p_R(G) = min{w(f) : f is a perfect Roman dominating function on G}. Let G̅ be the complement of a Graph G. The complementary prism GG̅ of G is the graph formed from the disjoint union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. This paper is devoted to the computation of perfect differentials of complementary prisms G G̅ and perfect Roman domination numbers of complementary prisms G G̅ by the use of the Gallai-type result proven before. Particular attention is given to the complementary prims of special types of graphs. Furthermore, a sharp lower bound on the perfect differential of the complementary prism G G̅ of a graph G in terms of the order of G is presented and the graphs attaining this lower bound are characterized. Finally, the graphs are characterized for which ∂_p(GG̅) and γ^p_R(GG̅) are small.