# On the $2$-packing differential of a graph

A. Cabrera Martínez(1), M.L. Puertas(2), J. A. Rodríguez-Velázquez(1)

(1)Universitat Rovira i Virgili, Departament d’Enginyeria Informàtica i
Matemàtiques
Av. Països Catalans 26, 43007 Tarragona, Spain.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
(2)Universidad de Almería, Departamento de Matemáticas
Carretera Sacramento s/n, 04120, Almería, Spain.
<EMAIL_ADDRESS>
###### Abstract

Let $G$ be a graph of order $\operatorname{n}(G)$ and vertex set $V(G)$. Given
a set $S\subseteq V(G)$, we define the external neighbourhood of $S$ as the
set $N_{e}(S)$ of all vertices in $V(G)\setminus S$ having at least one
neighbour in $S$. The differential of $S$ is defined to be
$\partial(S)=|N_{e}(S)|-|S|$. In this paper, we introduce the study of the
$2$-packing differential of a graph, which we define as
$\partial_{2p}(G)=\max\\{\partial(S):S\subseteq V(G)\text{ is a
}2\text{-packing}\\}.$ We show that the $2$-packing differential is closely
related to several graph parameters, including the packing number, the
independent domination number, the total domination number, the perfect
differential, and the unique response Roman domination number. In particular,
we show that the theory of $2$-packing differentials is an appropriate
framework to investigate the unique response Roman domination number of a
graph without the use of functions. Among other results, we obtain a Gallai-
type theorem, which states that
$\partial_{2p}(G)+\mu_{{}_{R}}(G)=\operatorname{n}(G)$, where
$\mu_{{}_{R}}(G)$ denotes the unique response Roman domination number of $G$.
As a consequence of the study, we derive several combinatorial results on
$\mu_{{}_{R}}(G)$, and we show that the problem of finding this parameter is
NP-hard. In addition, the particular case of lexicographic product graphs is
discussed.

Keywords: Unique response Roman domination, $2$-packing differential,
differential of a graph

##  1 Introduction

Given a graph $G=(V(G),E(G))$, the _open neighbourhood_ of a vertex $v$ of a
graph $G$ is defined to be $N(v)=\\{u\in V(G):\;u\text{ is adjacent to }v\\}$.
The _open neighbourhood of a set_ $S\subseteq V(G)$ is defined as
$N(S)=\cup_{v\in S}N(v)$, while the _external neighbourhood_ of $S$, or
boundary of $S$, is defined as $N_{e}(S)=N(S)\setminus S$. The _closed
neighbourhood_ of $v$ is $N[v]=N(v)\cup\\{v\\}$ and the _closed neighbourhood_
of a set $S\subseteq V(G)$ is $N[S]=N(S)\cup S$. We denote by $\deg(v)=|N(v)|$
the degree of vertex $v$, as well as $\delta(G)=\min_{v\in V(G)}\\{\deg(v)\\}$
the minimum degree of $G$, $\Delta(G)=\max_{v\in V(G)}\\{\deg(v)\\}$ the
maximum degree of $G$, $\operatorname{n}(G)=|V(G)|$ the order of $G$ and
$\operatorname{m}(G)=|E(G)|$ the size of $G$.

The _differential of a set_ $S\subseteq V(G)$ is defined as
$\partial(S)=|N_{e}(S)|-|S|$, while the _differential of a graph_ $G$ is
defined to be

$\partial(G)=\max\\{\partial(S):\,S\subseteq V(G)\\}.$

As described in [17], the definition of $\partial(G)$ was given by Hedetniemi
about twenty-five years ago in an unpublished paper, and was also considered
by Goddard and Henning [10]. After that, the differential of a graph has been
studied by several authors, including [2, 5, 17, 22, 24]

Lewis et al. [17] motivated the definition of differential from the following
game, what we call _graph differential game_. “ _You are allowed to buy as
many tokens as you like, say $k$ tokens, at a cost of one dollar each. You
then place the tokens on some subset $D$ of $k$ vertices of a graph $G$. For
each vertex of $G$ which has no token on it, but is adjacent to a vertex with
a token on it, you receive one dollar. Your objective is to maximize your
profit, that is, the total value received minus the cost of the tokens
bought_”. Obviously, $\partial(D)=|N_{e}(D)|-|D|$ is the profit obtained with
the placement $D$, while the maximum profit equals $\partial(G)$.

In order to introduce a variant of this game, we need the following
terminology. A set $S\subseteq V(G)$ is a $2$-_packing_ if $N[u]\cap
N[v]=\varnothing$ for every pair of different vertices $u,v\in S$. We define

$\wp(G)=\\{S\subseteq V(G):S\text{ is a }2\text{-packing of }G\\}.$

The $2$-_packing number_ of $G$, denoted by $\rho(G)$, is defined to be

$\rho(G)=\max\\{|S|:S\in\wp(G)\\}.$

Now, we consider a version of the graph differential game in which we impose
two additional conditions: (1) every vertex which has no token on it is
adjacent to at most one vertex with a token on it; and (2) no vertex with a
token on it is adjacent to a vertex with a token on it. In this case, any
placement $D$ of tokens is a $2$-packing and so this version of the game can
be called $2$-_packing graph differential game_ , as the maximum profit equals
the $2$-_packing differential_ of $G$, which is defined as

$\partial_{2p}(G)=\max\\{\partial(S):S\in\wp(G)\\}.$

We define a $\partial_{2p}(G)$-set as a set $S\in\wp(G)$ with
$\partial(S)=\partial_{2p}(G)$. The same agreement will be assumed for optimal
parameters associated to other characteristic sets defined in the paper.

Let $G$ be the graph shown in Figure 1. In the graph differential game, if we
place the tokens on vertices $a$, $b$ and $c$, then we obtain the maximum
profit $\partial(G)=7$. In contrast, in the $2$-packing graph differential
game, the maximum profit $\partial_{2p}(G)=6$ is given by the placement of
token on vertices $a$ and $b$.

$a$$b$$c$ Figure 1: A graph $G$ with $\partial(G)=7$ and $\partial_{2p}(G)=6$.

In this paper we show that the $2$-packing differential is closely related to
several graph parameters, including the packing number, the independent
domination number, the total domination number, the perfect differential, and
the unique response Roman domination number. In particular, we show that the
theory of $2$-packing differentials is an appropriate framework to investigate
the unique response Roman domination number of a graph without the use of
functions.

The rest of the paper is organized as follows. Section 2 is devoted to provide
some general bounds on the $2$-packing differential, in terms of different
parameters such as the maximum and minimum degrees of the graph, the number of
vertices, the number of edges, among others. We show that the bounds are tight
and, in some cases, we characterize the graphs achieving them. As a
consequence of the study, we show that the problem of finding
$\partial_{2p}(G)$ is NP-hard. In Section 3 we obtain a Nordhaus-Gaddum type
theorem for both the addition and the product of the $2$-packing differential
of a graph and its complement. Section 4 is devoted to the study of the
relationship between the $2$-packing differential and the perfect differential
of a graph. In Section 5 we prove a Gallai-type theorem which states that
$\partial_{2p}(G)+\mu_{{}_{R}}(G)=\operatorname{n}(G)$, where
$\mu_{{}_{R}}(G)$ denotes the unique response Roman domination number of $G$.
We derive several consequences of this result, including the fact that the
problem of finding $\mu_{{}_{R}}(G)$ is NP-hard. We finally show the case of
the lexicographic product graph in Section 6, where we obtain general lower
and upper bounds of the $2$-packing differential and the unique response Roman
domination number. We also compute the exact value of both parameters for the
lexicographic product of a path and any other graph.

##  2 Basic results and computational complexity

In this section we present lower and upper bounds of the $2$-packing
differential of a graph. In some cases, we also characterize the graphs
achieving such bounds. Moreover, these results will provide the computational
complexity of the computation of the $2$-packing differential.

We begin with the following theorem that will be a key result in the rest of
the paper. The bounds presented here are in terms of the maximum and minimum
degrees of the graph and the $2$-packing number.

######  Theorem 2.1.

If $G$ is a graph with no isolated vertex, then the following statements hold.

  1. (i)

$\partial_{2p}(G)=\displaystyle\max_{S\in\wp(G)}\left\\{\sum_{v\in
S}(deg(v)-1)\right\\}.$

  2. (ii)

If $G$ is a $k$-regular graph, then $\partial_{2p}(G)=(k-1)\rho(G).$

  3. (iii)

$\rho(G)(\delta(G)-1)\leq\partial_{2p}(G)\leq\rho(G)(\Delta(G)-1).$

  4. (iv)

$\partial_{2p}(G)=\rho(G)(\Delta(G)-1)$ if and only if there exists a
$\rho(G)$-set $S$ such that $\deg(v)=\Delta(G)$ for every $v\in S$.

  5. (v)

If $\partial_{2p}(G)=\rho(G)(\delta(G)-1)$, then every vertex $v$ in every
$\rho(G)$-set has degree $\deg(v)=\delta(G)$.

###### Proof.

Notice that for any $S\in\wp(G)$, we have that
$\displaystyle\partial(S)=|N(S)|-|S|=\sum_{v\in S}(deg(v)-1)$. Hence,
$\partial_{2p}(G)=\displaystyle\max_{S\in\wp(G)}\left\\{\partial(S)\right\\}=\max_{S\in\wp(G)}\left\\{|N(S)|-|S|\right\\}=\max_{S\in\wp(G)}\\{\sum_{v\in
S}(deg(v)-1)\\}.$ Therefore, (i) follows. From (i) we derive (ii) and (iii).

We proceed to prove (iv). If there exists a $\rho(G)$-set $S$ such that
$\deg(v)=\Delta(G)$ for every $v\in S$, then
$\rho(G)(\Delta(G)-1)=\partial(S)\leq\partial_{2p}(G)$. Hence, (iii) leads to
$\partial_{2p}(G)=\rho(G)(\Delta(G)-1)$. Conversely, if
$\partial_{2p}(G)=\rho(G)(\Delta(G)-1)$, then for any $\partial_{2p}(G)$-set
$D$ we have that $\rho(G)(\Delta(G)-1)=\partial(D)=\displaystyle\sum_{v\in
D}(deg(v)-1)\leq\displaystyle\sum_{v\in
D}(\Delta(G)-1)\leq|D|(\Delta(G)-1)\leq\rho(G)(\Delta(G)-1)$, which implies
that $D$ is a $\rho(G)$-set and $\deg(v)=\Delta(G)$ for every $v\in D$.

Finally, we prove (v). Suppose on the contrary that there exists a
$\rho(G)$-set $S^{\prime}$ and a vertex $v\in S^{\prime}$ such that
$\deg(v)>\delta(G)$. Then,
$\partial_{2p}(G)=\displaystyle\max_{S\in\wp(G)}\left\\{\sum_{v\in
S}(deg(v)-1)\right\\}\geq\sum_{v\in
S^{\prime}}(deg(v)-1)>\rho(G)(\delta(G)-1)$. Figure 2 shows an example of a
graph $G$ with $\partial_{2p}(G)=\rho(G)(\delta(G)-1)$, the set of black-
coloured vertices is the unique $\rho(G)$-set. ∎

Figure 2: A graph $G$ with $\partial_{2p}(G)=\rho(G)(\delta(G)-1)$.

The first consequence of the preceding result is the determination of the
complexity of the computation of the $2$-packing differential. Given a graph
$G$ and a positive integer $t$, the $2$-packing problem is to decide whether
there exists a $2$-packing $S$ in $G$ such that $|S|$ is at least $t$. It is
well known that the $2$-packing problem is NP-complete. Hence, the
optimization problem of finding $\rho(G)$ is NP-hard. Furthermore, it was
shown in [16] that the $2$-packing remains NP-complete for regular bipartite
graphs. Therefore, from Theorem 2.1 (ii) we derive the following result.

######  Corollary 2.2.

The problem of finding the $2$-packing differential of a graph is NP-hard,
even for regular bipartite graphs.

As a second consequence of Theorem 2.1 we can derive the exact value of the
$2$-packing differential in particular graph families. To this end, we need
the following definitions.

A set $S\subseteq V(G)$ of vertices is a _dominating set_ if $N(v)\cap
S\neq\varnothing$ for every vertex $v\in V(G)\setminus S$. Let
$\mathcal{D}(G)$ be the set of dominating sets of $G$. The _domination number_
of $G$ is defined to be,

$\gamma(G)=\min\\{|S|:\,S\in\mathcal{D}(G)\\}.$

Observe that $\gamma(G)\geq\rho(G)$ and
$\mathcal{D}(G)\cap\wp(G)\neq\varnothing$ if and only if there exists a
$\gamma(G)$-set which is a $\rho(G)$-set. A graph $G$ with
$\mathcal{D}(G)\cap\wp(G)\neq\varnothing$ is called an _efficient closed
domination graph_ and in such case $\gamma(G)=\rho(G)$ . Furthermore, Meir and
Moon [19] showed that $\gamma(T)=\rho(T)$ for every tree $T$. Even so, there
are trees in which $\mathcal{D}(T)\cap\wp(T)=\varnothing$.

If $G$ is a $k$-regular nonempty graph and there exists
$S\in\mathcal{D}(G)\cap\wp(G)$, then
$\operatorname{n}(G)=|S|+|N(S)|=|S|+|S|k=\rho(G)(1+k).$ Therefore, the
following result is a direct consequence of Theorem 2.1 (ii).

######  Corollary 2.3.

Let $k$ be a positive integer. If $G$ is a $k$-regular efficient closed
domination graph, then

$\partial_{2p}(G)=\frac{(k-1)\operatorname{n}(G)}{k+1}.$

The next statement is a direct consequence of Theorem 2.1 (i).

######  Corollary 2.4.

For any graph $G$ of diameter at most two, $\partial_{2p}(G)=\Delta(G)-1$.

We can also involve the order $n(G)$ and the size $m(G)$ of the graph and we
obtain the following upper bound of the $2$-packing differential.

######  Theorem 2.5.

For any graph $G$ with no isolated vertex,

$\partial_{2p}(G)\leq\rho(G)(\delta(G)-1)+2\operatorname{m}(G)-\operatorname{n}(G)\delta(G).$

Furthermore, the equality holds if and only if there exists a $\rho(G)$-set
$S$ such that $\deg(v)=\delta(G)$ for every $v\in V(G)\setminus S$.

###### Proof.

If $S\subseteq V(G)$ is a $\partial_{2p}(G)$-set, then

$\displaystyle 2\operatorname{m}(G)$ $\displaystyle=\sum_{v\in
S}\deg(v)+\sum_{v\not\in S}\deg(v)$
$\displaystyle=\partial_{2p}(G)+|S|+\sum_{v\not\in S}\deg(v)$
$\displaystyle\geq\partial_{2p}(G)+|S|+(\operatorname{n}(G)-|S|)\delta(G)$
$\displaystyle=\partial_{2p}(G)+\operatorname{n}(G)\delta(G)+|S|(1-\delta(G))$
$\displaystyle\geq\partial_{2p}(G)+\operatorname{n}(G)\delta(G)+\rho(G)(1-\delta(G)).$

Therefore, the upper bound follows.

From the previous procedure we deduce that if
$\partial_{2p}(G)=2\operatorname{m}(G)-\operatorname{n}(G)\delta(G)+(\delta(G)-1)\rho(G)$,
then $|S|=\rho(G)$ and $\deg(v)=\delta(G)$ for every $v\in V(G)\setminus S$.
Conversely, if $S$ is a $\rho(G)$-set and $\deg(v)=\delta(G)$ for every $v\in
V(G)\setminus S$, then the same procedure leads to
$2\operatorname{m}(G)-\operatorname{n}(G)\delta(G)+(\delta(G)-1)\rho(G)=\partial(S)\leq\partial_{2p}(G)$,
and by the upper bound we conclude that the equality holds. ∎

Notice that for any $k$-regular graph,
$2\operatorname{m}(G)=\operatorname{n}(G)\delta(G)=n(G)k$, which implies that
$\partial_{2p}(G)=(k-1)\rho(G)=2\operatorname{m}(G)-\operatorname{n}(G)\delta(G)+(\delta(G)-1)\rho(G).$

Figure 3: A graph $G$ with
$\partial_{2p}(G)=\rho(G)(\delta(G)-1)+2\operatorname{m}(G)-\operatorname{n}(G)\delta(G).$
The set of black-coloured vertices forms a $\partial_{2p}(G)$-set.

Figure 3 shows a graph $G$ with
$\partial_{2p}(G)=\rho(G)(\delta(G)-1)+2\operatorname{m}(G)-\operatorname{n}(G)\delta(G).$
Observe that the set $S$ of black-coloured vertices forms a $\rho(G)$-set with
$\deg(v)=\delta(G)$ for every $v\in V(G)\setminus S$.

The bound presented in Theorem 2.5 has a special behaviour in efficient closed
domination graphs, as we show in the following two results.

######  Theorem 2.6.

If $G$ is an efficient closed domination graph with no isolated vertex, then
the following statements hold.

  1. (i)

$\partial_{2p}(G)\geq\operatorname{n}(G)-2\rho(G).$

  2. (ii)

If there exists a $\rho(G)$-set $S$ such that $\deg(v)=\delta(G)$ for every
$v\in V(G)\setminus S$, then

$\partial_{2p}(G)=\operatorname{n}(G)-2\rho(G).$

###### Proof.

For any set $D\in\mathcal{D}(G)\cap\wp(G)$,

$\partial_{2p}(G)\geq\partial(D)=|N(D)|-|D|=|V(G)\setminus
D|-|D|=\operatorname{n}(G)-2\rho(G).$

Now, in order to prove (ii), let $S$ be a $\rho(G)$-set such that
$\deg(v)=\delta(G)$ for every $v\in V(G)\setminus S$. In the proof of Theorem
2.5 we have shown that $S$ is a $\partial_{2p}(G)$-set. Notice that
$|N(S)|\leq\operatorname{n}(G)-|S|=\operatorname{n}(G)-\rho(G)$. Hence,
$\operatorname{n}(G)-2\rho(G)\leq\partial_{2p}(G)=\partial(S)=|N(S)|-\rho(G)\leq\operatorname{n}(G)-2\rho(G)$.
Therefore, $\partial_{2p}(G)=\operatorname{n}(G)-2\rho(G).$ ∎

By Theorems 2.5 and 2.6 we deduce the following result.

######  Theorem 2.7.

For any efficient closed domination graph $G$ with $\delta(G)\geq 1$,

$\rho(G)\geq\left\lceil\frac{\operatorname{n}(G)(\delta(G)+1)-2\operatorname{m}(G)}{\delta(G)+1}\right\rceil.$

Furthermore, the equality holds if and only if there exists a $\rho(G)$-set
$S$ such that $\deg(v)=\delta(G)$ for every $v\in V(G)\setminus S$.

###### Proof.

By combining the bounds given in Theorems 2.5 and 2.6, we deduce that
$2\operatorname{m}(G)-\operatorname{n}(G)\delta(G)+(\delta(G)-1)\rho(G)\geq\partial_{2p}(G)\geq\operatorname{n}(G)-2\rho(G).$
Therefore, the bound follows.

Now, if
$\rho(G)=\frac{\operatorname{n}(G)(\delta(G)+1)-2\operatorname{m}(G)}{\delta(G)+1},$
then we have equalities in the above inequality chain, and by Theorem 2.5 we
conclude that there exists a $\rho(G)$-set $S$ such that $\deg(v)=\delta(G)$
for every $v\in V(G)\setminus S$.

Conversely, if there exists a $\rho(G)$-set $S$ such that $\deg(v)=\delta(G)$
for every $v\in V(G)\setminus S$, then Theorems 2.5 and 2.6 lead to
$2\operatorname{m}(G)-\operatorname{n}(G)\delta(G)+(\delta(G)-1)\rho(G)=\operatorname{n}(G)-2\rho(G),$
which implies that
$\rho(G)=\frac{\operatorname{n}(G)(\delta(G)+1)-2\operatorname{m}(G)}{\delta(G)+1}$.
∎

We now present lower and upper bounds of the $2$-packing differential in terms
of some dominating-type parameters. We begin with the following definition.

A set $S\subseteq V(G)$ which is both dominating and independent is called an
_independent dominating set_. Moreover, the _independent domination number_
$i(G)$ is

$i(G)=\min\\{|S|:\,S\text{ is an independent dominating set }\\}.$

In the following result we present both bounds and we characterize graphs
attaining the upper one.

######  Theorem 2.8.

For any graph $G$ with no isolated vertex,

$\Delta(G)-1\leq\partial_{2p}(G)\leq\frac{(\Delta(G)-1)(\operatorname{n}(G)-i(G))}{\Delta(G)}.$

Furthermore, the following statements are equivalent.

  1. (i)

$\partial_{2p}(G)=\frac{(\Delta(G)-1)(\operatorname{n}(G)-i(G))}{\Delta(G)}.$

  2. (ii)

There exist an $i(G)$-set $D$ and a $2$-packing $S\subseteq D$ such that
$N(S)\cup D=V(G)$ and $deg(v)=\Delta(G)$ for every $v\in S$.

###### Proof.

The lower bound is obtained by definition of $\partial_{2p}(G)$. Let $S$ be a
$\partial_{2p}(G)$-set, $S^{\prime}=\\{v\in V(G)\setminus N[S]:N(v)\subseteq
N(S)\\}$ and $S^{\prime\prime}=V(G)\setminus(N[S]\cup S^{\prime})$. Let
$S_{1}$ be an independent dominating set of the subgraph induced by
$S^{\prime\prime}$. Notice that this subgraph does not have isolated vertices,
which implies that $|S_{1}|<|S^{\prime\prime}|$. Also, observe that the set
$S\cup S^{\prime}\cup S_{1}$ is an independent dominating set of $G$. Hence,

$|N(S)|=\operatorname{n}(G)-(|S|-|S^{\prime}|-|S^{\prime\prime}|)\leq\operatorname{n}(G)-(|S|-|S^{\prime}|-|S_{1}|)\leq\operatorname{n}(G)-i(G).$

Also, notice that $|N(S)|\leq\Delta(G)|S|$. Hence,

$\displaystyle\Delta(G)\partial_{2p}(G)$ $\displaystyle=\Delta(G)(|N(S)|-|S|)$
$\displaystyle=\Delta(G)|N(S)|-\Delta(G)|S|$
$\displaystyle\leq\Delta(G)|N(S)|-|N(S)|$ $\displaystyle=(\Delta(G)-1)|N(S)|$
$\displaystyle\leq(\Delta(G)-1)(\operatorname{n}(G)-i(G)).$

Hence, the upper bound follows.

Now, if (i) holds, then we have equalities in the previous inequality chains.
From these, we deduce that $S^{\prime\prime}=\varnothing$, $D=S\cup
S^{\prime}$ is an $i(G)$-set, where $S$ is a $2$-packing and
$|N(S)|=\Delta(G)|S|=n-i(G)$, which implies that $N(S)\cup D=V(G)$ and
$deg(v)=\Delta(G)$ for every $v\in S$. Therefore, (ii) follows.

Finally, if (ii) holds, i.e., there exist an $i(G)$-set $D$ and a $2$-packing
$W\subseteq D$ such that $N(W)\cup D=V(G)$ and $deg(v)=\Delta(G)$ for every
$v\in W$, then $\Delta(G)|W|=|N(W)|=\operatorname{n}(G)-i(G)$ and so

$\partial_{2p}(G)\geq\partial(W)=|N(W)|-|W|=\operatorname{n}(G)-i(G)-\frac{\operatorname{n}(G)-i(G)}{\Delta(G)}.$

Therefore, from the upper bound we deduce that the equality holds. ∎

######  Corollary 2.9.

Let $G$ be a graph with no isolated vertex. If
$\Delta(G)=\operatorname{n}(G)-i(G)$, then $\partial_{2p}(G)=\Delta(G)-1$.

The converse of the result above does not hold. For instance, let $G$ be a
graph having a vertex $v\in V(G)$ of maximum degree
$deg(v)=\Delta(G)=\operatorname{n}(G)-3$ such that the two vertices in
$V(G)\setminus N[v]$ are adjacent. In this case, $i(G)=2$ and
$\partial_{2p}(G)=\operatorname{n}(G)-4=\Delta(G)-1$, while
$\Delta(G)<\operatorname{n}(G)-i(G)$.

Next, we consider a particular case of the equivalence given in Theorem 2.8.

######  Theorem 2.10.

For any graph $G$ with no isolated vertex,

$\partial_{2p}(G)\leq\operatorname{n}(G)-i(G)-1.$

Furthermore, the equality holds if and only if
$\Delta(G)=\operatorname{n}(G)-i(G)$.

###### Proof.

From Theorem 2.8 we deduce that $\operatorname{n}(G)-i(G)\geq\Delta(G)$ and
$\partial_{2p}(G)\leq\operatorname{n}(G)-i(G)-\frac{\operatorname{n}(G)-i(G)}{\Delta(G)}.$
Therefore, the upper bound follows.

Now, if $\Delta(G)=\operatorname{n}(G)-i(G)$, then from the bounds given in
Theorem 2.8 we deduce that $\partial_{2p}(G)=\operatorname{n}(G)-i(G)-1$.
Conversely, if $\partial_{2p}(G)=\operatorname{n}(G)-i(G)-1$, then by Theorem
2.8 we deduce that $\Delta(G)=\operatorname{n}(G)-i(G)$, which completes the
proof. ∎

We now characterize all trees attaining the lower bound presented in Theorem
2.8. To this end, we will use the following notation. Given a tree $T$, a
vertex $v\in V(T)$ with $\deg(v)=\Delta(T)$ and any vertex $v_{i}\in N(v)$,
denote by $T_{i}(v)$ the sub-tree of $T$ rooted in $v_{i}$ obtained from $T$
by removing the edge $\\{v,v_{i}\\}$. For each $i\in\\{1,\dots,\Delta(T)\\}$
such that $T_{i}(v)$ is non-trivial, denote by $w_{i}$ the neighbour of
$v_{i}$ in $T_{i}(v)$ with the largest degree.

######  Theorem 2.11.

Let $T$ be a non-trivial tree. Then, $\partial_{2p}(T)=\Delta(T)-1$ if and
only if, for each vertex $v\in V(T)$ with $\deg(v)=\Delta(T)$, the following
conditions hold.

  1. (i)

$\operatorname{ecc}(v)\leq 3$,

  2. (ii)

$\deg(v_{i})+\sum_{j\neq i}(\deg(w_{j})-1)\leq\Delta(T)$,
($i=1,\dots,\Delta(T)$ and $j\neq i$ with $T_{j}(v)$ non-trivial),

  3. (iii)

$\sum_{i}(\deg(w_{i})-1)\leq\Delta(T)-1$, ($i\in\\{1,\dots,\Delta(T)\\}$ such
that $T_{i}(v)$ is non-trivial).

###### Proof.

Assume that $\partial_{2p}(T)=\Delta(T)-1$ and take $v\in V(T)$ with
$\deg(v)=\Delta(T)$. The distance between two vertices $x,y\in V(T)$ will be
denoted by $d(x,y)$.

If there exists $w\in V(T)$ such that $d(v,w)=4$, then for $u\in N(w)$ with
$d(v,u)=3$ the set $\\{v,u\\}$ is a $2$-packing and $\deg(u)\geq 2$. Thus,
$\partial_{2p}(T)\geq\partial(\\{v,u\\})\geq(\deg(u)-1)+(\deg(v)-1)>\deg(v)-1=\Delta(T)-1$,
which is a contradiction. Therefore, $\operatorname{ecc}(v)\leq 3$.

The vertex set $X=\\{v_{i}\\}\cup\\{w_{j}\colon j\neq i,T_{j}(v)\text{ is non-
trivial}\\}$ is a $2$-packing, so $\partial(X)=(\deg(v_{i})-1)+\sum_{j\neq
i}(\deg(w_{j})-1)\leq\partial_{2p}(T)=\Delta(T)-1$, that gives (ii).
Analogously, the set $\\{w_{i}\colon T_{i}(v)\text{ is non-trivial}\\}$ is a
$2$-packing and this gives (iii).

Now, let $T$ be a non-trivial tree satisfying (i), (ii) and (iii), let $S$ be
a $2$-packing of $T$ and let $v$ be a vertex with $\deg(v)=\Delta(T)$. Since
$\partial_{2p}(T)\geq\Delta(T)-1$, we proceed to show that
$\partial_{2p}(T)\leq\Delta(T)-1$. To this end, we differentiate the following
three cases.

Case 1: $v\in S$. If there exists $u\in S\setminus\\{v\\}$, then $d(u,v)\geq
3$ and condition (i) gives that $\deg(u)=1$ (see Figure 4). Therefore,
$\partial(S)=\sum_{w\in S}(deg(w)-1)=\deg(v)-1=\Delta(T)-1$.

Case 2: $v_{i}\in S$, for some $v_{i}\in N(v)$. Notice that $N[v]\cap
S=\\{v_{i}\\}$ and, if there exists $u\in S\setminus\\{v_{i}\\}$, then
$d(u,v_{i})\geq 3$. In such a case, $u$ belongs to a non-trivial rooted sub-
tree $T_{j}(v)$, $j\neq i$ and $d(u,v)\geq 2$ (see Figure 4). Clearly, $S\cap
V(T_{j}(v))=\\{u\\}$ and from (ii) we obtain $\partial(S)=\sum_{w\in
S}(deg(w)-1)\leq(\deg(v_{i})-1)+\sum_{j\neq i}(\deg(w_{j})-1)\leq\Delta(T)-1$.

Case 3: $N[v]\cap S=\emptyset$. Then every vertex $u\in S$ satisfies
$d(u,v)\geq 2$ and from (iii) we obtain $\partial(S)=\sum_{w\in
S}(deg(w)-1)\leq\sum_{i}(\deg(w_{i})-1)\leq\Delta(T)-1$. ∎

Figure 4: A tree with $\partial_{2p}(T)=\Delta(T)-1=4$. The set of black-
coloured vertices is a $\partial_{2p}(T)$-set and the set of grey-coloured
vertices is another one.

Some upper bounds of the $2$-packing differential can be also expressed in
terms of the total domination number. A set $S\subseteq V(G)$ is a _total
dominating set_ of a graph $G$ without isolated vertices if every vertex $v\in
V(G)$ is adjacent to at least one vertex in $S$. Let $\mathcal{D}_{t}(G)$ be
the set of total dominating sets of $G$. The _total domination number_ of $G$
is defined to be,

$\gamma_{t}(G)=\min\\{|S|:\,S\in\mathcal{D}_{t}(G)\\}.$

By definition, $\mathcal{D}_{t}(G)\subseteq\mathcal{D}(G)$, so that
$\gamma(G)\leq\gamma_{t}(G)$. Furthermore, $\gamma_{t}(G)\leq 2\gamma(G)$.

######  Lemma 2.12.

Let $G$ be a graph with no isolated vertex. Let $S$ be a
$\partial_{2p}(G)$-set such that $|S|$ is maximum among all
$\partial_{2p}(G)$-sets, $S^{\prime}=\\{v\in V(G)\setminus N[S]:N(v)\subseteq
N(S)\\}$ and $S^{\prime\prime}=V(G)\setminus(N[S]\cup S^{\prime})$. The
following statements hold.

  1. (i)

$N(v)\cap N(S)\neq\varnothing$ for every $v\in S^{\prime\prime}$.

  2. (ii)

$\gamma_{t}(G)\leq 2|S|+|S^{\prime}|+|S^{\prime\prime}|$.

  3. (iii)

If $\gamma_{t}(G)=2|S|+|S^{\prime}|+|S^{\prime\prime}|$, then $S^{\prime}\cup
S^{\prime\prime}=\varnothing.$

###### Proof.

Suppose that there exists a vertex $v\in S^{\prime\prime}$ such that
$N(v)\subseteq S^{\prime\prime}$. Notice that $S_{v}=S\cup\\{v\\}$ is a
$2$-packing of $G$ and that $\partial(S_{v})\geq\partial(S)=\partial_{2p}(G)$,
which is a contradiction because $|S_{v}|>|S|$. Hence, for every $v\in
S^{\prime\prime}$, it follows that $N(v)\cap N(S)\neq\varnothing$.

Now, we define $W^{\prime}$ as a set of minimum cardinality among the sets
$W\subseteq N(S)$ satisfying that $N(x)\cap W\neq\varnothing$ for every $x\in
S\cup S^{\prime}\cup S^{\prime\prime}$.

Notice that $S\cup W^{\prime}$ is a total dominating set of $G$, which implies
that $\gamma_{t}(G)\leq|S|+|W^{\prime}|\leq
2|S|+|S^{\prime}|+|S^{\prime\prime}|$.

In order to prove (iii) assume
$\gamma_{t}(G)=2|S|+|S^{\prime}|+|S^{\prime\prime}|$. In this case,
$|W^{\prime}|=|S|+|S^{\prime}|+|S^{\prime\prime}|$. Suppose that there exists
$x\in S^{\prime}\cup S^{\prime\prime}$. Since there exists $y\in N(x)\cap
W^{\prime}\cap N(S)$, the minimality of $|W^{\prime}|$ leads to
$|W^{\prime}|<|S|+|S^{\prime}|+|S^{\prime\prime}|$, which is a contradiction.
Therefore, $S^{\prime}\cup S^{\prime\prime}=\varnothing.$ ∎

######  Theorem 2.13.

For any graph $G$ with no isolated vertex,

$\partial_{2p}(G)\leq\operatorname{n}(G)-\gamma_{t}(G).$

Furthermore, the equality holds if and only if $G$ is an efficient closed
domination graph with $\gamma_{t}(G)=2\gamma(G)$.

###### Proof.

Let $S$ be a $\partial_{2p}(G)$-set such that $|S|$ is maximum among all
$\partial_{2p}(G)$-sets, $S^{\prime}=\\{v\in V(G)\setminus N[S]:N(v)\subseteq
N(S)\\}$ and $S^{\prime\prime}=V(G)\setminus(N[S]\cup S^{\prime})$. By Lemma
2.12, $\gamma_{t}(G)\leq 2|S|+|S^{\prime}|+|S^{\prime\prime}|$. Hence,

$\partial_{2p}(G)=|N(S)|-|S|=\operatorname{n}(G)-2|S|-|S^{\prime}|-|S^{\prime\prime}|\leq\operatorname{n}(G)-\gamma_{t}(G).$

Therefore, the upper bound follows.

Now, if $\mathcal{D}(G)\cap\wp(G)\neq\varnothing$ and
$\gamma_{t}(G)=2\gamma(G)$, then from the upper bound above and the lower
bound given in Theorem 2.6 we deduce that
$\partial_{2p}(G)=\operatorname{n}(G)-\gamma_{t}(G)$. Conversely, if
$\partial_{2p}(G)=\operatorname{n}(G)-\gamma_{t}(G)$, then we have equalities
in the above inequality chain. In particular, we deduce that
$2|S|+|S^{\prime}|+|S^{\prime\prime}|=\gamma_{t}(G)$, and Lemma 2.12 leads to
$S^{\prime}\cup S^{\prime\prime}=\varnothing$. Hence,
$S\in\mathcal{D}(G)\cap\wp(G)$ and so, $\gamma_{t}(G)=2|S|=2\gamma(G)$, which
completes the proof. ∎

######  Theorem 2.14.

For any graph $G$ with no isolated vertex,

$\partial_{2p}(G)\leq\frac{2\operatorname{m}(G)+\rho(G)(\delta(G)-1)-\gamma_{t}(G)\delta(G)}{\delta(G)+1}.$

Furthermore, the equality holds if and only if $\gamma_{t}(G)=2\gamma(G)$ and
there exists a set $S\in\mathcal{D}(G)\cap\wp(G)$ such that
$\deg(v)=\delta(G)$ for every $v\in V(G)\setminus S$.

###### Proof.

Let $S$ be a $\partial_{2p}(G)$-set such that $|S|$ is maximum among all
$\partial_{2p}(G)$-sets, and let $m^{\prime}$ be the size of the subgraph of
$G$ induced by $V(G)\setminus S$. Notice that every vertex in $N(S)$ has
exactly one neighbour in $S$, which implies that

$m^{\prime}=\frac{1}{2}\left(\displaystyle\sum_{v\in
N(S)}(\deg(v)-1)+\sum_{v\in V(G)\setminus N[S]}\deg(v)\right).$

Observe that Lemma 2.12 leads to $\gamma_{t}(G)\leq 2|S|+|V(G)\setminus
N[S]|$. Hence,

$\displaystyle\operatorname{m}(G)$ $\displaystyle=\sum_{v\in
S}\deg(v)+m^{\prime}$
$\displaystyle=\left(\partial_{2p}(G)+|S|\right)+\frac{1}{2}\left(\displaystyle\sum_{v\in
N(S)}(\deg(v)-1)+\sum_{v\in V(G)\setminus N[S]}\deg(v)\right),\,\text{ by
Theorem \ref{th-packings} (i),}$
$\displaystyle\geq\partial_{2p}(G)+|S|+\frac{1}{2}\left(|N(S)|(\delta(G)-1)+(\gamma_{t}(G)-2|S|)\delta(G)\right)$
$\displaystyle\geq\partial_{2p}(G)+\frac{1}{2}(|S|+(|S|-|N(S)|)+(|N(S)|-|S|)\delta(G)+\gamma_{t}(G)\delta(G)-|S|\delta(G))$
$\displaystyle=\partial_{2p}(G)+\frac{1}{2}\left(\partial_{2p}(G)(\delta(G)-1)-(\delta(G)-1)|S|+\gamma_{t}(G)\delta(G)\right)$
$\displaystyle\geq\partial_{2p}(G)+\frac{1}{2}\left(\partial_{2p}(G)(\delta(G)-1)-(\delta(G)-1)\rho(G)+\gamma_{t}(G)\delta(G)\right).$

Therefore, the upper bound follows.

Now, if the bound is achieved, then from the previous procedure we deduce that
$\deg(v)=\delta(G)$ for every $v\in V(G)\setminus S$, $|S|=\rho(G)$ and
$\gamma_{t}(G)=2|S|+|V(G)\setminus
N[S]|=\operatorname{n}(G)-\partial_{2p}(G)$. Thus, by Theorem 2.13 we conclude
that $\mathcal{D}(G)\cap\wp(G)\neq\varnothing$ and $\gamma_{t}(G)=2\gamma(G)$.
Conversely, if $\gamma_{t}(G)=2\gamma(G)$ and there exists a set
$D\in\mathcal{D}(G)\cap\wp(G)$ such that $\deg(v)=\delta(G)$ for every $v\in
V(G)\setminus D$, then the same procedure leads to

$2\operatorname{m}(G)+\rho(G)(\delta(G)-1)-\gamma_{t}(G)\delta(G)=(\delta(G)+1)\partial(D)\leq(\delta(G)+1)\partial_{2p}(G),$

and by the upper bound we conclude that the equality holds. ∎

To conclude this section, we derive some bounds in terms of the order of $G$.

######  Theorem 2.15.

The following statements hold for any graph $G$ with no isolated vertex.

  1. (i)

If $k\in\\{1,2,3\\}$ and $\Delta(G)=\operatorname{n}(G)-k$, then
$\partial_{2p}(G)=\operatorname{n}(G)-k-1.$

  2. (ii)

If $\Delta(G)\leq\operatorname{n}(G)-4$, then
$\partial_{2p}(G)\leq\operatorname{n}(G)-4$ and the equality holds if and only
if $G$ is an efficient closed domination graph with $\gamma(G)=2$.

###### Proof.

Assume $\Delta(G)=\operatorname{n}(G)-k$. If $k\in\\{1,2\\}$, then $\rho(G)=1$
and so $\partial_{2p}(G)=\Delta(G)-1=\operatorname{n}(G)-k-1$. Now, let $S$ be
a $\partial_{2p}(G)$-set. If $k=3$ then either $\rho(G)=1$, and we proceed as
above, or $|S|\geq 2$, which implies that
$\operatorname{n}(G)-4=\Delta(G)-1\leq\partial_{2p}(G)=\partial(S)=|N(S)|-|S|\leq\operatorname{n}(G)-2|S|\leq\operatorname{n}(G)-4.$
Therefore, (i) follows.

From now on, assume $\Delta(G)\leq\operatorname{n}(G)-4$. Let $S$ be a
$\partial_{2p}(G)$-set. If $|S|=1$, then
$\partial_{2p}(G)=\Delta(G)-1\leq\operatorname{n}(G)-5.$ Now, if $|S|\geq 2$,
then
$\partial_{2p}(G)=\partial(S)=|N(S)|-|S|\leq\operatorname{n}(G)-2|S|\leq\operatorname{n}(G)-4.$
Therefore, the equality $\partial_{2p}(G)=\partial(S)=\operatorname{n}(G)-4$
holds if and only if $S\in\mathcal{D}(G)\cap\wp(G)$ and $|S|=2$. ∎

##  3 Nordhaus-Gaddum type relations

Nordhaus and Gaddum [20] in 1956 proposed lower and upper bounds, in terms of
the order of the graph, on the sum and the product of the chromatic number of
a graph and its complement. Since then, several inequalities of a similar type
have been proposed for other graph parameters. In this section we derive some
Nordhaus-Gaddum type relations for the $2$-packing differential.

A set $S\subseteq V(G)$ is an _open packing_ if $N(u)\cap N(v)=\varnothing$
for every pair of different vertices $u,v\in S$. The _open packing number_ of
$G$, denoted by $\rho_{o}(G)$, is the maximum cardinality among all open
packings of $G$. A graph $G$ is an _efficient open domination graph_ if there
exists an open packing which is a dominating set.

Notice that the complement of $G$, denoted by $G^{c}$, is an efficient closed
domination graph with $\gamma(G^{c})=2$ if and only if $G$ is an efficient
open domination graph with $\rho_{o}(G)=2$.

By Theorem 2.15 and the lower bound given in Theorem 2.8, we deduce the
following result.

######  Theorem 3.1.

Given a graph $G$, the following statements hold.

  * •

If $\Delta(G)=\operatorname{n}(G)-2$ and $\delta(G)=1$, then
$\partial_{2p}(G)+\partial_{2p}(G^{c})=2\operatorname{n}(G)-6$ and
$\partial_{2p}(G)\cdot\partial_{2p}(G^{c})=(\operatorname{n}(G)-3)^{2}$.

  * •

If $\Delta(G)=\operatorname{n}(G)-2$ and $\delta(G)=2$, then
$\partial_{2p}(G)+\partial_{2p}(G^{c})=2\operatorname{n}(G)-7$ and
$\partial_{2p}(G)\cdot\partial_{2p}(G^{c})=(\operatorname{n}(G)-3)(\operatorname{n}(G)-4)$.

  * •

If $\Delta(G)=\operatorname{n}(G)-3$ and $\delta(G)=1$, then
$\partial_{2p}(G)+\partial_{2p}(G^{c})=2\operatorname{n}(G)-7$ and
$\partial_{2p}(G)\cdot\partial_{2p}(G^{c})=(\operatorname{n}(G)-3)(\operatorname{n}(G)-4)$.

  * •

If $\Delta(G)=\operatorname{n}(G)-3$ and $\delta(G)=2$, then
$\partial_{2p}(G)+\partial_{2p}(G^{c})=2\operatorname{n}(G)-8$ and
$\partial_{2p}(G)\cdot\partial_{2p}(G^{c})=(\operatorname{n}(G)-4)^{2}$.

  * •

If $\Delta(G)=\operatorname{n}(G)-2$ and $\delta(G)\geq 3$, then

$2\operatorname{n}(G)-\delta(G)-5\leq\partial_{2p}(G)+\partial_{2p}(G^{c})\leq
2\operatorname{n}(G)-7,$
$(\operatorname{n}(G)-3)(\operatorname{n}(G)-\delta(G)-2)\leq\partial_{2p}(G)\cdot\partial_{2p}(G^{c})\leq(\operatorname{n}(G)-3)(\operatorname{n}(G)-4).$

  * •

If $\Delta(G)=\operatorname{n}(G)-2$ and $\delta(G)\geq 3$, then
$\partial_{2p}(G)+\partial_{2p}(G^{c})=2\operatorname{n}(G)-7$ if and only if
$\partial_{2p}(G)\cdot\partial_{2p}(G^{c})=(\operatorname{n}(G)-3)(\operatorname{n}(G)-4)$
if and only if $G$ is an efficient open domination graph with $\rho_{o}(G)=2$.

  * •

If $\Delta(G)=\operatorname{n}(G)-3$ and $\delta(G)\geq 3$, then

$2\operatorname{n}(G)-\delta(G)-6\leq\partial_{2p}(G)+\partial_{2p}(G^{c})\leq
2\operatorname{n}(G)-8,$
$(\operatorname{n}(G)-4)(\operatorname{n}(G)-\delta(G)-2)\leq\partial_{2p}(G)\cdot\partial_{2p}(G^{c})\leq(\operatorname{n}(G)-4)^{2}.$

  * •

If $\Delta(G)=\operatorname{n}(G)-3$ and $\delta(G)\geq 3$, then
$\partial_{2p}(G)+\partial_{2p}(G^{c})=2\operatorname{n}(G)-8$ if and only if
$\partial_{2p}(G)\cdot\partial_{2p}(G^{c})=(\operatorname{n}(G)-4)^{2}$ if and
only if $G$ is an efficient open domination graph with $\rho_{o}(G)=2$.

  * •

If $\Delta(G)\leq\operatorname{n}(G)-4$ and $\delta(G)=1$, then

$\operatorname{n}(G)+\Delta(G)-4\leq\partial_{2p}(G)+\partial_{2p}(G^{c})\leq
2\operatorname{n}(G)-7,$
$(\Delta(G)-1)(\operatorname{n}(G)-3)\leq\partial_{2p}(G)\cdot\partial_{2p}(G^{c})\leq(\operatorname{n}(G)-3)(\operatorname{n}(G)-4).$

  * •

If $\Delta(G)\leq\operatorname{n}(G)-4$ and $\delta(G)=1$, then
$\partial_{2p}(G)+\partial_{2p}(G^{c})=2\operatorname{n}(G)-7$ if and only if
$\partial_{2p}(G)\cdot\partial_{2p}(G^{c})=(\operatorname{n}(G)-4)(\operatorname{n}(G)-3)$
if and only if $G$ is an efficient closed domination graph with $\gamma(G)=2$.

  * •

If $\Delta(G)\leq\operatorname{n}(G)-4$ and $\delta(G)=2$, then

$\operatorname{n}(G)+\Delta(G)-5\leq\partial_{2p}(G)+\partial_{2p}(G^{c})\leq
2\operatorname{n}(G)-8,$
$(\Delta(G)-1)(\operatorname{n}(G)-4)\leq\partial_{2p}(G)\cdot\partial_{2p}(G^{c})\leq(\operatorname{n}(G)-4)^{2}.$

  * •

If $\Delta(G)\leq\operatorname{n}(G)-4$ and $\delta(G)=2$, then
$\partial_{2p}(G)+\partial_{2p}(G^{c})=2\operatorname{n}(G)-8$ if and only if
$\partial_{2p}(G)\cdot\partial_{2p}(G^{c})=(\operatorname{n}(G)-4)^{2}$ if and
only if $G$ is an efficient closed domination graph with $\gamma(G)=2$.

  * •

If $\Delta(G)\leq\operatorname{n}(G)-4$ and $\delta(G)\geq 3$, then

$\operatorname{n}(G)+\Delta(G)-\delta(G)-3\leq\partial_{2p}(G)+\partial_{2p}(G^{c})\leq
2\operatorname{n}(G)-8.$
$(\Delta(G)-1)(\operatorname{n}(G)-\delta(G)-2)\leq\partial_{2p}(G)\cdot\partial_{2p}(G^{c})\leq(\operatorname{n}(G)-4)^{2}.$

  * •

If $\Delta(G)\leq\operatorname{n}(G)-4$ and $\delta(G)\geq 3$, then
$\partial_{2p}(G)+\partial_{2p}(G^{c})=2\operatorname{n}(G)-8$ if and only if
$\partial_{2p}(G)\cdot\partial_{2p}(G^{c})=(\operatorname{n}(G)-4)^{2}$ if and
only if $G$ is simultaneously an efficient closed domination and an efficient
open domination graph with $\rho_{o}(G)=\gamma(G)=2$.

##  4 Perfect differential versus $2$-packing differential

In this section we show some relationships between the $2$-packing
differential and the perfect differential of a graph. Given a set $S\subseteq
V(G)$ and a vertex $v\in S$, the _external private neighbourhood_
$\operatorname{epn}(v,S)$ of $v$ with respect to $S$ is defined to be
$\operatorname{epn}(v,S)=\\{u\in V(G)\setminus S:\,N(u)\cap S=\\{v\\}\\}$. The
_perfect neighbourhood of a set_ $S\subseteq V(G)$ is defined to be
$N_{p}(S)=\\{v\in V(G)\setminus S:\,|N(v)\cap S|=1\\}$. We define the _perfect
differential of a set_ $S\subseteq V(G)$ as $\partial_{p}(S)=|N_{p}(S)|-|S|$.
The _perfect differential of a graph_ , introduced by Cabrera Martínez and
Rodríguez-Velázquez in [5], is defined as

$\partial_{p}(G)=\max\\{\partial_{p}(S):\,S\subseteq V(G)\\}.$

Now, $S\subseteq V(G)$ is a _perfect dominating set_ of $G$ if every vertex in
$V(G)\setminus S$ is adjacent to exactly one vertex in $S$. Let
$\mathcal{D}^{p}(G)$ be the set of perfect dominating sets of $G$. The
_perfect domination number_ of $G$ is defined to be,

$\gamma^{p}(G)=\min\\{|S|:\,S\in\mathcal{D}^{p}(G)\\}.$

Notice that $\mathcal{D}^{p}(G)\subseteq\mathcal{D}(G)$, which implies that
$\gamma(G)\leq\gamma^{p}(G)$.

######  Theorem 4.1.

[5] Given a nontrivial graph $G$, the following inequality chain holds.

$\operatorname{n}(G)-2\gamma^{p}(G)\leq\partial_{p}(G)\leq\frac{\operatorname{n}(G)(\Delta(G)-1)}{\Delta(G)+1}.$

Furthermore,
$\partial_{p}(G)=\frac{\operatorname{n}(G)(\Delta(G)-1)}{\Delta(G)+1}$ if and
only if $\gamma^{p}(G)=\frac{\operatorname{n}(G)}{\Delta(G)+1}$.

The following theorems show some relationships between the $2$-packing
differential and the perfect differential.

######  Theorem 4.2.

For any nontrivial graph $G$, the following statements hold.

  1. (i)

$\partial_{2p}(G)\leq\partial_{p}(G).$

  2. (ii)

$\partial_{2p}(G)\leq\frac{\operatorname{n}(G)(\Delta(G)-1)}{\Delta(G)+1}.$

  3. (iii)

$\partial_{2p}(G)=\frac{\operatorname{n}(G)(\Delta(G)-1)}{\Delta(G)+1}$ if and
only if $\gamma^{p}(G)=\frac{\operatorname{n}(G)}{\Delta(G)+1}$.

###### Proof.

Let $S$ be a $\partial_{2p}(G)$-set. Since $S$ is a $2$-packing,
$N(S)=N_{p}(S)$. Hence,
$\partial_{2p}(G)=\partial(S)=|N(S)|-|S|=|N_{p}(S)|-|S|=\partial_{p}(S)\leq\partial_{p}(G)$.
Therefore, (i) follows.

Notice that (ii) is a direct consequence of (i) and Theorem 4.1. We proceed to
prove (iii). It is known that
$\gamma^{p}(G)\geq\gamma(G)\geq\frac{\operatorname{n}(G)}{\Delta(G)+1}$ and
$\gamma(G)=\frac{\operatorname{n}(G)}{\Delta(G)+1}$ if and only if there
exists a $\gamma(G)$-set $S$ which is a $\rho(G)$-set and every vertex in $S$
has degree $\Delta(G)$, for instance, see [12]. Hence, by Theorem 2.1, if
$\gamma^{p}(G)=\frac{\operatorname{n}(G)}{\Delta(G)+1}$, then

$\partial_{2p}(G)=\displaystyle\max_{S\in\wp(G)}\left\\{\sum_{v\in
S}(deg(v)-1)\right\\}=\rho(G)(\Delta(G)-1)=\frac{\operatorname{n}(G)(\Delta(G)-1)}{\Delta(G)+1}.$

Conversely, if
$\partial_{2p}(G)=\frac{\operatorname{n}(G)(\Delta(G)-1)}{\Delta(G)+1}$, then
by (i) and Theorem 4.1 we have that
$\partial_{p}(G)=\frac{\operatorname{n}(G)(\Delta(G)-1)}{\Delta(G)+1}$.
Therefore, Theorem 4.1 leads to
$\gamma^{p}(G)=\frac{\operatorname{n}(G)}{\Delta(G)+1}$. ∎

The difference $\partial_{p}(G)-\partial_{2p}(G)$ can be as large as desired.
Consider the graph obtained by attaching to each vertex of a $5$-cycle a set
of $k$ independent vertices. The resulting graph $G$ has order $n(G)=5k+5$ and
satisfies $\partial_{p}(G)=5k-5$ (the set of vertices of the $5$-cycle is a
$\partial_{p}(G)$-set) and $\partial_{2p}(G)=k+1$ (each single vertex in the
$5$-cycle is a $\partial_{2p}(G)$-set). Moreover, the set of vertices of the
$5$-cycle is a minimum perfect dominating set, so $\gamma^{p}(G)=5$ and
$\partial_{p}(G)=n(G)-2\gamma^{p}(G)$ takes the smallest possible value.

Regarding the case in which both parameters agree, we have the following
result.

######  Theorem 4.3.

For any graph $G$, at least one of the following statements hold.

  1. (i)

$\partial_{2p}(G)=\partial_{p}(G)$.

  2. (ii)

$\partial_{2p}(G)\geq\frac{1}{2}(\Delta(G)\partial_{p}(G)+2-(\operatorname{n}(G)-2)(\Delta(G)-2))$.

###### Proof.

By Theorem 4.2 we have that $\partial_{2p}(G)\leq\partial_{p}(G)$. From now
on, we assume that $\partial_{2p}(G)<\partial_{p}(G)$. Let $S$ be a
$\partial_{p}(G)$-set. Since $\partial_{p}(G)=|N_{p}(S)|-|S|$ and
$|N_{p}(S)|+|S|\leq\operatorname{n}(G)$, it follows that
$|S|\leq(\operatorname{n}(G)-\partial_{p}(G))/2$. Let $S^{\prime}\subseteq S$
be maximal $2$-packing and $S^{\prime\prime}=S\setminus S^{\prime}$. Observe
that $S$ is not a $2$-packing, as
$\partial_{2p}(G)<\partial_{p}(G)=\partial(S)$. Hence,
$N[S^{\prime\prime}]\cap N(S^{\prime})\neq\varnothing$, which implies that

$|N_{p}(S)|=|N(S^{\prime})\setminus N[S^{\prime\prime}]|+\sum_{x\in
S^{\prime\prime}}|epn(x,S)|\leq(|N(S^{\prime})|-1)+|S^{\prime\prime}|(\Delta(G)-1).$

Thus,

$\displaystyle\partial_{p}(G)$ $\displaystyle=|N_{p}(S)|-|S|$
$\displaystyle\leq(|N(S^{\prime})|-1)+|S^{\prime\prime}|(\Delta(G)-1)-|S|$
$\displaystyle=\partial(S^{\prime})+|S^{\prime}|-1+|S^{\prime\prime}|(\Delta(G)-1)-|S|$
$\displaystyle=\partial(S^{\prime})-1+|S^{\prime\prime}|(\Delta(G)-2)$
$\displaystyle\leq\partial_{2p}(G)-1+(|S|-1)(\Delta(G)-2)$
$\displaystyle\leq\partial_{2p}(G)-1+\left(\frac{\operatorname{n}(G)-\partial_{p}(G)}{2}-1\right)(\Delta(G)-2).$

Therefore, the result follows. ∎

The bound above is tight. For instance, for any integer $t\geq 2$, the double
star $S_{t,t}$ satisfies that $\partial_{p}(S_{t,t})=2t-2$,
$\partial_{2p}(S_{t,t})=t$, $\operatorname{n}(S_{t,t})=2t+2$ and
$\Delta(S_{t,t})=t+1$. Hence, the bound is achieved by any double star
$S_{t,t}$ with $t\geq 2$.

##  5 Unique response Roman domination versus $2$-packing differential

In this section we establish a Gallai-type theorem which states the
relationship between the $2$-packing differential and the unique response
Roman domination number.

Cockayne, Hedetniemi and Hedetniemi [7] defined a Roman dominating function on
a graph $G$ to be a function $f:V(G)\longrightarrow\\{0,1,2\\}$ satisfying the
condition that every vertex $u$ for which $f(u)=0$ is adjacent to at least one
vertex $v$ for which $f(v)=2$. For $X\subseteq V(G)$ we define the weight of
$X$ as $f(X)=\sum_{v\in X}f(v)$. The weight of $f$ is defined to be

$\omega(f)=f(V(G)).$

The unique response version of Roman domination was introduced by Rubalcaba
and Slater in [23] and studied further in [9, 14, 29]. A function
$f:V(G)\longrightarrow\\{0,1,2\\}$ with the sets $V_{0},V_{1},V_{2}$, where
$V_{i}=\\{v\in V(G):\,f(v)=i\\}$ for $i\in\\{0,1,2\\}$, is a _unique response
Roman dominating function_ if $x\in V_{0}$ implies $|N(x)\cap V_{2}|=1$ and
$x\in V_{1}\cup V_{2}$ implies that $N(x)\cap V_{2}=\varnothing$. 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$.

######  Theorem 5.1 (Gallai-type theorem).

For any graph $G$,

$\mu_{{}_{R}}(G)+\partial_{2p}(G)=\operatorname{n}(G).$

###### Proof.

It was shown in [9] that
$\mu_{{}_{R}}(G)=\displaystyle\min_{S\subseteq\wp(G)}\\{2|S|+|V(G)\setminus(N(S)\cup
S)|\\}$. Hence, the result is deduced as follows.

$\displaystyle\mu_{{}_{R}}(G)$
$\displaystyle=\min_{S\subseteq\wp(G)}\\{2|S|+|V(G)\setminus(N(S)\cup S)|\\}$
$\displaystyle=\min_{S\subseteq\wp(G)}\\{2|S|+\operatorname{n}(G)-(|N(S)|+|S|)|\\}$
$\displaystyle=\min_{S\subseteq\wp(G)}\\{\operatorname{n}(G)-\partial(S)\\}$
$\displaystyle=\operatorname{n}(G)-\max_{S\subseteq\wp(G)}\\{\partial(S)\\}$
$\displaystyle=\operatorname{n}(G)-\partial_{2p}(G).$

∎

Theorem 5.1 allows us to derive results on the unique response Roman
domination number from results on the $2$-packing differential and vice versa.
For instance, from Corollary 2.2 and Theorem 5.1 we deduce the following
result.

######  Theorem 5.2.

The problem of finding the unique response Roman domination number of a graph
is NP-hard, even for regular bipartite graphs.

Theorem 5.1 suggests the challenge of obtaining new results on the unique
response Roman domination number from the approach of $2$-packing
differentials. As an example, the following table summarizes some of those
results obtained here. The first column describes the result that combined
with Theorem 5.1 leads to the result on the second column.

From | Result for graphs with no isolated vertex
---|---
Theorem 2.1 (iii) |  $\mu_{{}_{R}}(G)\geq\operatorname{n}(G)-\rho(G)(\Delta(G)-1)$.
| The equality holds if and only if there exists a $\rho(G)$-set $S$ such that
|  $\deg(v)=\Delta(G)$ for every $v\in S$.
Theorem 2.5 |  $\mu_{{}_{R}}(G)\geq\operatorname{n}(G)(\delta(G)+1)-\rho(G)(\delta(G)-1)-2\operatorname{m}(G)$.
| The equality holds if and only if there exists a $\rho(G)$-set $S$ such that
|  $\deg(v)=\delta(G)$ for every $v\in V(G)\setminus S$.
Theorem 2.6 | If $G$ is an efficient closed domination graph, then $\mu_{{}_{R}}(G)\leq 2\rho(G).$
| In particular, if there exists a $\rho(G)$-set $S$ such that
$\deg(v)=\delta(G)$
| for every $v\in V(G)\setminus S$, then $\mu_{{}_{R}}(G)=2\rho(G).$
Theorem 2.8 | $\mu_{{}_{R}}(G)\geq\frac{\operatorname{n}(G)+(\Delta(G)-1)i(G)}{\Delta(G)}.$
Theorem 2.10 | $\mu_{{}_{R}}(G)\geq i(G)+1.$
| The equality holds if and only if $\Delta(G)=\operatorname{n}(G)-i(G)$.
Theorem 2.13 | $\mu_{{}_{R}}(G)\geq\gamma_{t}(G).$
| The equality holds if and only if $G$ is an efficient closed domination
| graph and $\gamma_{t}(G)=2\gamma(G)$.
Theorem 2.14 | $\mu_{{}_{R}}(G)\geq\frac{\operatorname{n}(G)(\delta(G)+1)-2\operatorname{m}(G)-\rho(G)(\delta(G)-1)+\gamma_{t}(G)\delta(G)}{\delta(G)+1}.$
| The equality holds if and only if there exists a set
|  $S\in\mathcal{D}(G)\cap\wp(G)$ such that $\deg(v)=\delta(G)$ for every
$v\in V(G)\setminus S$.
Theorem 4.2 (i) |  $\mu_{{}_{R}}(G)\geq\operatorname{n}(G)-\partial_{p}(G)$.
Theorem 4.2 (ii) |  $\mu_{{}_{R}}(G)=\frac{2\operatorname{n}(G)}{\Delta(G)+1}$ if and only if $\gamma^{p}(G)=\frac{\operatorname{n}(G)}{\Delta(G)+1}$.

##  6 The case of lexicographic product graphs

In this final section we present the behaviour of the $2$-packing differential
under the lexicographic product operation. We first recall the following
definition. Let $G$ and $H$ be two graphs. The _lexicographic product_ of $G$
and $H$ is the graph $G\circ H$ whose vertex set is $V(G\circ H)=V(G)\times
V(H)$ and $(u,v)(x,y)\in E(G\circ H)$ if and only if $ux\in E(G)$ or $u=x$ and
$vy\in E(H)$. Notice that for any $u\in V(G)$ the subgraph of $G\circ H$
induced by $\\{u\\}\times V(H)$ is isomorphic to $H$. For simplicity, we will
denote this subgraph by $H_{u}$.

For a basic introduction to the lexicographic product of two graphs we suggest
the books [11, 13]. One of the main problems in the study of $G\circ H$
consists of finding exact values or tight bounds of specific parameters of
these graphs and express them in terms of known invariants of $G$ and $H$. In
particular, we cite the following works on domination theory of lexicographic
product graphs: (total) domination [18, 21, 28], Roman domination [25], weak
Roman domination [27], rainbow domination [26], super domination [8], doubly
connected domination [1], secure domination [15], double domination [3] and
total Roman domination [6, 4].

The following claim, which states the distance formula in the lexicographic
product of two graphs, is one of our main tools.

######  Remark 6.1.

[11] For any connected graph $G$ of order $\operatorname{n}(G)\geq 2$ and any
graph $H$, the following statements hold.

  1. (i)

$d_{G\circ H}((g,h),(g^{\prime},h^{\prime}))=d_{G}(g,g^{\prime})$ for $g\neq
g^{\prime}$.

  2. (ii)

$d_{G\circ H}((g,h),(g,h^{\prime}))=\min\\{2,d_{H}(h,h^{\prime})\\}$.

Given a set $W\subseteq V(G)\times V(H)$, the projection of $W$ on $V(G)$ will
be denoted by $P_{G}(W)$. The following corollary is a direct consequence of
the previous remark.

######  Corollary 6.2.

Let $G$ be a connected graph of order $\operatorname{n}(G)\geq 2$ and let $H$
be a graph. A set $W\subseteq V(G)\times V(H)$ is a $2$-packing of $G\circ H$
if and only if $P_{G}(W)$ is a $2$-packing of $G$ and $|W|=|P_{G}(W)|$.

In the following result we show general lower and upper bounds for the
$2$-packing differential of a lexicographic product graph, in terms of some
parameters of both factors.

We define the following parameter.

$\rho^{\prime}(G)=\max\\{|S|:\,S\text{ is a }\partial_{2p}(G)\text{-set}\\}.$

######  Theorem 6.3.

For any connected graph $G$ of order $\operatorname{n}(G)\geq 2$ and any graph
$H$,

$\operatorname{n}(H)\partial_{2p}(G)+\rho^{\prime}(G)(\operatorname{n}(H)+\Delta(H)-1)\leq\partial_{2p}(G\circ
H)\leq\operatorname{n}(H)\partial_{2p}(G)+\rho(G)(\operatorname{n}(H)+\Delta(H)-1).$

Furthermore,

$\operatorname{n}(H)\mu_{{}_{R}}(G)-\rho(G)(\operatorname{n}(H)+\Delta(H)-1)\leq\mu_{{}_{R}}(G\circ
H)\leq\operatorname{n}(H)\mu_{{}_{R}}(G)-\rho^{\prime}(G)(\operatorname{n}(H)+\Delta(H)-1).$

###### Proof.

Let $W\subseteq V(G)\times V(H)$ be a $\partial_{2p}(G\circ H)$-set and
$U=P_{G}(W)$. By Corollary 6.2, we learned that $U$ is a $2$-packing of $G$.
Hence,

$\displaystyle\partial_{2p}(G\circ H)$ $\displaystyle=|N(W)|-|W|$
$\displaystyle=\sum_{(g,h)\in W}|N(g)|\operatorname{n}(H)+\sum_{(g,h)\in
W}\deg(h)-|W|$ $\displaystyle\leq|N(U)|\operatorname{n}(H)+|U|\Delta(H)-|U|$
$\displaystyle=\partial(U)\operatorname{n}(H)+|U|(\operatorname{n}(H)+\Delta(H)-1)$
$\displaystyle\leq\partial_{2p}(G)\operatorname{n}(H)+\rho(G)(\operatorname{n}(H)+\Delta(H)-1)).$

Now, for any $\partial_{2p}(G)$-set $S$ with $|S|=\rho^{\prime}(G)$ and any
$v\in V(H)$ with $\deg(v)=\Delta(H)$, the set $S\times\\{v\\}$ is a
$2$-packing of $G\circ H$, and so

$\displaystyle\partial_{2p}(G\circ H)$
$\displaystyle\geq\partial(S\times\\{v\\})$ $\displaystyle=\sum_{u\in
S}(|N(u)|\operatorname{n}(H)+\Delta(H))-\rho^{\prime}(G)$
$\displaystyle=|N(S)|\operatorname{n}(H)+\Delta(H)\rho^{\prime}(G)-\rho^{\prime}(G)$
$\displaystyle=\partial(S)\operatorname{n}(H)+\rho^{\prime}(G)(\operatorname{n}(H)+\Delta(H)-1)$
$\displaystyle=\partial_{2p}(G)\operatorname{n}(H)+\rho^{\prime}(G)(\operatorname{n}(H)+\Delta(H)-1).$

By Theorem 5.1 we complete the proof. ∎

If $G$ is a regular graph, then $\rho(G)=\rho^{\prime}(G)$. Hence, from
Theorem 6.3 we derive the following result.

######  Corollary 6.4.

The following statements hold for any connected regular graph $G$ of order
$\operatorname{n}(G)\geq 2$ and any graph $H$.

  * •

$\partial_{2p}(G\circ
H)=\operatorname{n}(H)\partial_{2p}(G)+\rho(G)(\operatorname{n}(H)+\Delta(H)-1).$

  * •

$\mu_{{}_{R}}(G\circ
H)=\operatorname{n}(H)\mu_{{}_{R}}(G)-\rho(G)(\operatorname{n}(H)+\Delta(H)-1).$

If $G$ is an efficient closed domination graph with
$\partial_{2p}(G)=\operatorname{n}(G)-2\rho(G)$, then
$\rho(G)=\rho^{\prime}(G)$. Therefore, Theorem 6.3 leads to the following
result.

######  Corollary 6.5.

If $G$ is a connected efficient closed domination graph with
$\operatorname{n}(G)\geq 2$ and
$\partial_{2p}(G)=\operatorname{n}(G)-2\rho(G)$, then the following statements
hold for any graph $H$,

  * •

$\partial_{2p}(G\circ
H)=\operatorname{n}(H)\partial_{2p}(G)+\rho(G)(\operatorname{n}(H)+\Delta(H)-1).$

  * •

$\mu_{{}_{R}}(G\circ
H)=\operatorname{n}(H)\mu_{{}_{R}}(G)-\rho(G)(\operatorname{n}(H)+\Delta(H)-1).$

We finish with the computation of the exact values of the $2$-packing
differential and the unique response Roman domination number of the
lexicographic product of a path and any other graph.

######  Theorem 6.6.

Let $r\geq 2$ be an integer. If $H$ is a nonempty graph, then

$\partial_{2p}(P_{r}\circ
H)=\displaystyle\left\\{\begin{array}[]{ll}\frac{r}{3}\left(2\operatorname{n}(H)+\Delta(H)-1\right),&r\equiv
0\pmod{3},\\\\[6.0pt]
\frac{2}{3}(r-1)\operatorname{n}(H)+\frac{r+2}{3}(\Delta(H)-1),&r\equiv
1\pmod{3},\\\\[6.0pt]
\frac{2r-1}{3}\operatorname{n}(H)+\frac{r+1}{3}(\Delta(H)-1),&r\equiv
2\pmod{3}.\end{array}\right.$

Furthermore,

$\mu_{{}_{R}}(P_{r}\circ
H)=\displaystyle\left\\{\begin{array}[]{ll}\frac{r}{3}\left(\operatorname{n}(H)-\Delta(H)+1\right),&r\equiv
0\pmod{3},\\\\[6.0pt] \frac{r+2}{3}(\operatorname{n}(H)-\Delta(H)+1),&r\equiv
1\pmod{3},\\\\[6.0pt] \frac{r+1}{3}(\operatorname{n}(H)-\Delta(H)+1),&r\equiv
2\pmod{3}.\end{array}\right.$

###### Proof.

If $r\equiv 0,2\pmod{3}$, then $\rho^{\prime}(P_{r})=\rho(P_{r})$. Hence, the
result follows from Theorem 6.3. Now, assume $r\equiv 1\pmod{3}$, and let $S$
be a $\rho(P_{r})$-set. In this case, $P_{r}$ is an efficient closed
domination graph, and so $|N(S)|=r-|S|=\frac{2(r-1)}{3}$. Thus, for every
vertex $v\in V(H)$ with $\deg(v)=\Delta(H)$,

$\displaystyle\partial_{2p}(P_{r}\circ H)$
$\displaystyle\geq\partial(S\times\\{v\\})$ $\displaystyle=\sum_{u\in
S}(|N(u)|\operatorname{n}(H)+\Delta(H)-1)$
$\displaystyle=|N(S)|\operatorname{n}(H)+\rho(P_{r})(\Delta(H)-1)$
$\displaystyle=\frac{2}{3}(r-1)\operatorname{n}(H)+\frac{r+2}{3}(\Delta(H)-1).$

It remains to show that the equality holds. To this end, let $W$ be a
$\partial_{2p}(P_{r}\circ H)$-set and $U$ the projection of $W$ on $V(P_{r})$.
By Corollary 6.2, we learned that $U$ is a $2$-packing of $P_{r}$. Hence, as
in the proof of Theorem 6.3 we deduce that $\partial_{2p}(P_{r}\circ
H)\leq|N(U)|\operatorname{n}(H)+|U|(\Delta(H)-1).$ Thus, if $U$ is a
$\rho(P_{r})$-set, then $\partial_{2p}(P_{r}\circ
H)=\frac{2}{3}(r-1)\operatorname{n}(H)+\frac{r+2}{3}(\Delta(H)-1)$, as
required. Now, suppose to the contrary, that
$|U|\leq\rho(P_{r})-1=\frac{r-1}{3}$. In such a case, $|N(U)|\leq
2|U|\leq\frac{2(r-1)}{3}$, and so

$\displaystyle\frac{2}{3}(r-1)\operatorname{n}(H)+\frac{r+2}{3}(\Delta(H)-1)$
$\displaystyle\leq\partial_{2p}(P_{r}\circ H)$
$\displaystyle\leq|N(U)|\operatorname{n}(H)+|U|(\Delta(H)-1)$
$\displaystyle\leq\frac{2}{3}(r-1)\operatorname{n}(H)+\frac{r-1}{3}(\Delta(H)-1),$

which is a contradiction for $\Delta(H)\geq 2$, and we have equalities for
$\Delta(H)=1$.

By Theorem 5.1 we complete the proof. ∎

We can make the appropriate modifications in the proof of the previous theorem
to show that the following result follows.

######  Theorem 6.7.

Let $r\geq 2$ be an integer. If $H$ is an empty graph, then

$\partial_{2p}(P_{r}\circ
H)=\displaystyle\left\\{\begin{array}[]{ll}\frac{r}{3}\left(2\operatorname{n}(H)-1\right),&r\equiv
0\pmod{3},\\\\[6.0pt] \frac{r-1}{3}(2\operatorname{n}(H)-1),&r\equiv
1\pmod{3},\\\\[6.0pt] \frac{2r-1}{3}\operatorname{n}(H)-\frac{r+1}{3},&r\equiv
2\pmod{3}.\end{array}\right.$

Furthermore,

$\mu_{{}_{R}}(P_{r}\circ
H)=\displaystyle\left\\{\begin{array}[]{ll}\frac{r}{3}\left(\operatorname{n}(H)+1\right),&r\equiv
0\pmod{3},\\\\[6.0pt] \frac{r+2}{3}\operatorname{n}(H)+\frac{r-1}{3},&r\equiv
1\pmod{3},\\\\[6.0pt] \frac{r+1}{3}(\operatorname{n}(H)+1),&r\equiv
2\pmod{3}.\end{array}\right.$

## References

  * [1] B. H. Arriola, S. R. Canoy, Jr., Doubly connected domination in the corona and lexicographic product of graphs, Appl. Math. Sci. (Ruse) 8 (29-32)(2014) 1521–1533.
  * [2] S. Bermudo, J. C. Hernández-Gómez, J. M. Rodríguez, J. M. Sigarreta, Relations between the differential and parameters in graphs, Electronic Notes in Discrete Mathematics 46 (2014) 281–288.
  * [3] A. Cabrera Martínez, S. Cabrera García, J. A. Rodríguez-Velázquez, Double domination in lexicographic product graphs, Discrete Appl. Math. 284 (2020) 290–300.
  * [4] A. Cabrera Martínez, J. A. Rodríguez-Velázquez, Closed formulas for the total Roman domination number of lexicographic product graphs, Ars Math. Contemp. (2021) In press. https://doi.org/10.26493/1855-3974.2284.aeb
  * [5] A. Cabrera Martínez, J. A. Rodríguez-Velázquez, On the perfect differential of a graph, Quaest. Math. (2021) In press.
https://doi.org/10.2989/16073606.2020.1858992

  * [6] N. Campanelli, D. Kuziak, Total Roman domination in the lexicographic product of graphs, Discrete Appl. Math. 263 (2019) 88–95.
  * [7] E. J. Cockayne, P. A. Dreyer Jr., S. M. Hedetniemi, S. T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (1–3) (2004) 11–22.
  * [8] M. Dettlaff, M. Lemańska, J. A. Rodríguez-Velázquez, R. Zuazua, On the super domination number of lexicographic product graphs, Discrete Appl. Math. 263 (2019) 118–129.
  * [9] E. Ebrahimi Targhi, N. Jafari Rad, L. Volkmann, Unique response Roman domination in graphs, Discrete Appl. Math. 159 (11) (2011) 1110–1117.
  * [10] W. Goddard, M. A. Henning, Generalised domination and independence in graphs, Congr. Numer. 123 (1997) 161–171.
  * [11] R. Hammack, W. Imrich, S. Klavžar, Handbook of product graphs, Discrete Mathematics and its Applications, 2nd ed., CRC Press, 2011.
  * [12] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Chapman and Hall/CRC Pure and Applied Mathematics Series, Marcel Dekker, Inc. New York, 1998.
  * [13] W. Imrich, S. Klavžar, Product graphs, structure and recognition, Wiley-Interscience series in discrete mathematics and optimization, Wiley, 2000.
  * [14] N. Jafari Rad, C.-H. Liu, Trees with strong equality between the Roman domination number and the unique response Roman domination number, Australas. J. Combin. 54 (2012) 133–140.
  * [15] D. J. Klein, J. A. Rodríguez-Velázquez, Protection of lexicographic product graphs, Discuss. Math. Graph Theory. In press. https://doi.org/10.7151/dmgt.2243
  * [16] M. C. Kong, Y. Zhao, On computing maximum $k$-independent sets, in: Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993), vol. 95, 1993.
  * [17] J. L. Lewis, T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, P. J. Slater, Differentials in graphs, Util. Math. 69 (2006) 43–54.
  * [18] J. Liu, X. Zhang, J. Meng, Domination in lexicographic product digraphs, Ars Combin. 120 (2015) 23–32.
  * [19] A. Meir, J. W. Moon, Relations between packing and covering numbers of a tree, Pacific Journal of Mathematics 61 (1) (1975) 225–233.
  * [20] E. A. Nordhaus, J. W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175–177.
  * [21] R. J. Nowakowski, D. F. Rall, Associative graph products and their independence, domination and coloring numbers, Discussiones Mathematicae Graph Theory 16 (1996) 53–79.
  * [22] P. R. L. Pushpam, D. Yokesh, Differentials in certain classes of graphs, Tamkang J. Math. 41 (2) (2010) 129–138.
  * [23] R. R. Rubalcaba, P. J. Slater, Roman dominating influence parameters, Discrete Math. 307 (24) (2007) 3194–3200.
  * [24] J. M. Sigarreta, Differential in Cartesian product graphs, Ars Combin. 126 (2016) 259–267.
  * [25] T. K. Šumenjak, P. Pavlič, A. Tepeh, On the Roman domination in the lexicographic product of graphs, Discrete Appl. Math. 160 (13-14) (2012) 2030–2036.
  * [26] T. K. Šumenjak, D. F. Rall, A. Tepeh, Rainbow domination in the lexicographic product of graphs, Discrete Appl. Math. 161 (13-14) (2013) 2133–2141.
  * [27] M. Valveny, H. Pérez-Rosés, J. A. Rodríguez-Velázquez, On the weak Roman domination number of lexicographic product graphs, Discrete Appl. Math. 263 (2019) 257–270.
  * [28] X. Zhang, J. Liu, J. Meng, Domination in lexicographic product graphs, Ars Combin. 101 (2011) 251–256.
  * [29] N. Zhao, W. Li, T. Zhao, Z. Zhang, The unique response Roman domination in trees, J. Combin. Math. Combin. Comput. 105 (2018) 165–183.