On the perfect differential and perfect Roman domination in complementary prisms.

Saved in:

Bibliographic Details
Title:	On the perfect differential and perfect Roman domination in complementary prisms.
Authors:	Berberler, Zeynep Nihan¹ (AUTHOR) zeynep.berberler@deu.edu.tr
Source:	RAIRO: Operations Research (2804-7303). 2025, Vol. 59 Issue 2, p1247-1256. 10p.
Subjects:	Prisms, Neighborhoods, Graph theory, Dominating set
Abstract:	Let G = (V, E) be a graph of order n. For S ⊆ V (G), the set Np(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) = \|Np(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 γpR(G), is the minimum weight among all perfect Roman dominating functions on G, that is γpR(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 GG̅ and perfect Roman domination numbers of complementary prisms GG̅ 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 GG̅ 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 γpR(GG̅) are small. [ABSTRACT FROM AUTHOR]
	Copyright of RAIRO: Operations Research (2804-7303) is the property of EDP Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	Let G = (V, E) be a graph of order n. For S ⊆ V (G), the set Np(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) = \|Np(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 γpR(G), is the minimum weight among all perfect Roman dominating functions on G, that is γpR(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 GG̅ and perfect Roman domination numbers of complementary prisms GG̅ 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 GG̅ 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 γpR(GG̅) are small. [ABSTRACT FROM AUTHOR]
ISSN:	28047303
DOI:	10.1051/ro/2025039