RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 2024 Volume 115, Issue 6, Pages 868–876 (Mi mzm13993)

Papers published in the English version of the journal

Unique Response Roman Domination Versus 2-Packing Differential in Complementary Prisms

Z. Berberler, M. Çerezci

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

Abstract: Let $G = (V,E)$ be a graph of order $n$. For $S \subseteq V(G)$, the set $N_e(S)$ is defined as the external neighborhood of $S$ such that all vertices in $V(G)\backslash S$ have at least one neighbor in $S$. The differential of $S$ is defined to be $\partial(S)=|N_e(S)|-|S|$, and the 2-packing differential of a graph is defined as
$$ \partial_{2p}(G) =\max\{\partial(S)\colon S \subseteq V(G) \text{ is a 2-packing}\}. $$
A function $f\colon V(G) \to \{0,1,2\}$ with the sets $V_0,V_1,V_2$, where
$$ V_i =\{v\in V(G)\colon f(v) = i\},\qquad i \in \{0,1,2\}, $$
is a unique response Roman dominating function if $x \in V_0 $ implies that $| N( x ) \cap V_2 | = 1$ and $x \in V_1 \cup V_2 $ implies that $N( x ) \cap V_2 = \emptyset$. The unique response Roman domination number of $G$, denoted by $\mu_R(G)$, is the minimum weight among all unique response Roman dominating functions on $G$. Let $\bar{G}$ be the complement of a graph $G$. The complementary prism $G\bar {G}$ of $G$ is the graph formed from the disjoint union of $G$ and $\bar {G}$ by adding the edges of a perfect matching between the respective vertices of $G$ and $\bar {G}$. The present paper deals with the computation of the 2-packing differential and the unique response Roman domination of the complementary prisms $G\bar {G}$ by the use of a proven Gallai-type theorem. Particular attention is given to the complementary prims of special types of graphs. Furthermore, the graphs $G$ such that $\partial_{2p} ( G\bar G)$ and $\mu _R(G\bar G)$ are small are characterized.

Keywords: differential of a graph, 2-packing differential of a graph, unique response Roman domination, complementary prism.

MSC: 05C69

Received: 17.04.2023
Revised: 05.04.2024

Language: English


 English version:
Mathematical Notes, 2024, 115:6, 868–876

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024