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.
Citation:
Z. Berberler, M. Çerezci, “Unique Response Roman Domination Versus 2-Packing Differential in Complementary Prisms”, Math. Notes, 115:6 (2024), 868–876