Статьи, опубликованные в английской версии журнала
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
Аннотация:
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.
Ключевые слова:
differential of a graph, 2-packing differential of a graph, unique response Roman domination, complementary prism.
MSC: 05C69 Поступило: 17.04.2023
Исправленный вариант: 05.04.2024
Язык публикации: английский