# From the strong differential to Italian domination in graphs

A. Cabrera Martínez, J. A. Rodríguez-Velázquez
Universitat Rovira i Virgili
Departament d’Enginyeria Informàtica i Matemàtiques
Av. Països Catalans 26, 43007 Tarragona, Spain.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Given a graph $G$ and a subset of vertices $D\subseteq V(G)$, the external
neighbourhood of $D$ is defined as $N_{e}(D)=\\{u\in V(G)\setminus
D:\,N(u)\cap D\neq\varnothing\\}$, where $N(u)$ denotes the open neighbourhood
of $u$. Now, given a subset $D\subseteq V(G)$ and a vertex $v\in D$, the
external private neighbourhood of $v$ with respect to $D$ is defined to be
$\operatorname{epn}(v,D)=\\{u\in V(G)\setminus D:\,N(u)\cap D=\\{v\\}\\}.$ The
strong differential of a set $D\subseteq V(G)$ is defined as
$\partial_{s}(D)=|N_{e}(D)|-|D_{w}|,$ where $D_{w}=\\{v\in
D:\,\operatorname{epn}(v,D)\neq\varnothing\\}$. In this paper we focus on the
study of the strong differential of a graph, which is defined as

$\partial_{s}(G)=\max\\{\partial_{s}(D):\,D\subseteq V(G)\\}.$

Among other results, we obtain general bounds on $\partial_{s}(G)$ and we
prove a Gallai-type theorem, which states that
$\partial_{s}(G)+\gamma_{{}_{I}}(G)=\operatorname{n}(G)$, where
$\gamma_{{}_{I}}(G)$ denotes the Italian domination number of $G$. Therefore,
we can see the theory of strong differential in graphs as a new approach to
the theory of Italian domination. One of the advantages of this approach is
that it allows us to study the Italian domination number without the use of
functions. As we can expect, we derive new results on the Italian domination
number of a graph.

Keywords: Italian domination; (strong) differential of a graph

##  1 Introduction

Given a graph $G=(V(G),E(G))$ and a vertex $v\in V(G)$, the open neighbourhood
of $v$ is defined to be $N(v)=\\{u\in V(G):\,uv\in E(G)\\}$. 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 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 [19], 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 [9]. After that, the differential of a graph has been
studied by several authors, including [1, 2, 3, 5, 19, 20].

Lewis et al. [19] 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)$.

Given a set $D\subseteq V(G)$ and a vertex $v\in D$, the external private
neighbourhood of $v$ with respect to $D$ is defined to be

$\operatorname{epn}(v,D)=\\{u\in V(G)\setminus D:\,N(u)\cap D=\\{v\\}\\}.$

We define the sets $D_{w}=\\{v\in
D:\,\operatorname{epn}(v,D)\neq\varnothing\\}$ and $D_{s}=D\setminus D_{w}$.

We consider a version of the graph differential game in which you will get a
refund of one dollar for each token placed in a vertex with no external
private neighbour with respect to $D$, i.e., we will get a refund of one
dollar for a token placed in a vertex $v$ if either every neighbour of $v$ has
a token on it or every neighbour of $v$ which has no token on it is also
adjacent to a vertex different from $v$ with a token on it. This version of
the game can be called graph differential game with refund. Thus, we define
the strong differential of $D$, denoted by $\partial_{s}(D)$, as the profit
obtained with the placement $D$ in the graph differential game with refund,
which is $\partial_{s}(D)=|N_{e}(D)|-|D_{w}|$. Notice that

$\partial_{s}(D)=|N_{e}(D)|-|D_{w}|=|N_{e}(D)|-|D|+|D_{s}|=\partial(D)+|D_{s}|.$

In the graph differential game with refund, the maximum profit equals the
strong differential of $G$, which is defined as

$\partial_{s}(G)=\max\\{\partial_{s}(D):\,D\subseteq V(G)\\}.$

For instance, consider the graph $G$ shown in Figure 1. If $D$ is the set of
(gray and black) coloured vertices, and we place a token in each vertex
belonging to $D$, then in the graph differential game with refund we get a
refund of four dollars, as the black-coloured vertices do not have external
private neighbours with respect to $D$. Although the gray-coloured vertex has
four neighbours not belonging to $D$, it only contributes in three dollars to
the profit, as it does not produce any refund. Hence, the total profit
obtained with the placement $D$ equals
$\partial_{s}(D)=|N_{e}(D)|-|D_{w}|=9-1=8$. Notice that for this graph, the
maximum profit equals $\partial_{s}(G)=\partial_{s}(D)=8$.

Figure 1: A graph $G$ with $\partial_{s}(G)=8$.

Suppose that one “entity” is stationed at some of the vertices of a graph $G$
and that an entity at a vertex can deal with a problem at any vertex in its
neighbourhood. In general, an entity could consist of a robot, an observer, a
legion, a guard, and so on. In this sense, given a set $D\subseteq V(G)$, we
say that all vertices in $N(D)$ are defended by the vertices in $D$. The whole
graph is deemed protected under $D$ if every vertex not in $D$ has a neighbour
in $D$, and in such a case we say that $D$ is a protector of $G$. A vertex
$u\in N_{e}(D)$ is strongly defended under $D$ if $|N(u)\cap D|\geq 2$,
otherwise $u$ is weakly defended under $D$. Now, a vertex $v\in D$ is a weak
defender with respect to $D$ if $\operatorname{epn}(v,D)\neq\varnothing$, as
there are vertices which are only defended by $v$, and so $v$ does not have
any help to defend its private neighbours. The set of weak defenders with
respect to $D$ is $D_{w}$, while any $v\in D_{s}=D\setminus D_{w}$ will be a
strong defender with respect to $D$. In this sense, we can see the strong
differential $\partial_{s}(D)=|N_{e}(D)|-|D_{w}|$ as a manner of quantify the
quality of the protection of $G$ with the placement $D$ of entities. In this
case, we have a penalty of one unit per each weak defender in $D$. With this
approach, the strong differential allows us to compare two protectors, i.e.,
the larger $\partial_{s}(D)$ is, the better protector the set $D$ is. In
Section 3 we will show that for any graph, there exists a protector
(dominating set) $D$ with $\partial_{s}(D)=\partial_{s}(G)$. Thus,
$\partial_{s}(G)$ quantifies the maximum quality among the protectors of $G$.
In the same section we will see that the concept of strong differential is
closely related to the theory of Italian domination, which is one of the
approaches to protection of graphs. In that section, the role of weak and
strong defenders will be clearly shown.

The remainder of the paper is organized as follows. In Section 2 we introduce
some notation and tools needed to develop the remaining sections. In Section 3
we prove a Gallai-type theorem which states that
$\partial_{s}(G)+\gamma_{{}_{I}}(G)=\operatorname{n}(G)$, where
$\gamma_{{}_{I}}(G)$ denotes the Italian domination number of $G$. We conclude
the section showing that the problem of finding $\partial_{s}(G)$ is NP-hard.
Section 4 is devoted to provide general results on the strong differential. We
obtain tight bounds, we show some classes of graphs for which the bounds are
achieved and, in some cases, we characterize the graphs achieving the bounds.
Some of these results are derived from known results on the Italian domination
number, while from others we can infer new results on this invariant. The
paper ends with a brief concluding remark section (Section 5) where we
summarize some of these results.

##  2 Notation, terminology and basic tools

Throughout the paper, we will use the notation $G\cong H$ if $G$ and $H$ are
isomorphic graphs. The closed neighbourhood of a vertex $v$ is defined as
$N[v]=N(v)\cup\\{v\\}$. Given a set $S\subseteq V(G)$, $N[S]=N(S)\cup S$ and
the subgraph of $G$ induced by $S$ will be denoted by $G[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$ and $\operatorname{n}(G)=|V(G)|$
the order of $G$. A leaf of $G$ is a vertex of degree one. A support vertex of
$G$ is a vertex which is adjacent to a leaf. The set of leaves and support
vertices of $G$ will be denoted by $\mathcal{L}(G)$ and $\mathcal{S}(G)$,
respectively.

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)\\}.$

The domination number has been extensively studied. For instance, we cite the
following books, [11, 12].

We define a $\gamma(G)$-set as a set $S\in\mathcal{D}(G)$ with
$|S|=\gamma(G)$. The same agreement will be assumed for optimal parameters
associated to other characteristic sets defined in the paper. For instance, a
$\partial_{s}(G)$-set will be a set $D\subseteq V(G)$ such that
$\partial_{s}(D)=\partial_{s}(G)$.

A set $S$ of vertices of $G$ is a vertex cover if every edge of $G$ is
incident with at least one vertex in $S$. The vertex cover number of $G$,
denoted by $\beta(G)$, is the minimum cardinality among all vertex covers of
$G$. Recall that the largest cardinality of a set of vertices of $G$, no two
of which are adjacent, is called the independence number of $G$ and it is
denoted by $\alpha(G)$. The following well-known result, due to Gallai, states
the relationship between the independence number and the vertex cover number
of a graph.

######  Theorem 2.1 (Gallai’s theorem, [8]).

For any graph $G$,

$\alpha(G)+\beta(G)=\operatorname{n}(G).$

Let $f:V(G)\longrightarrow\\{0,1,2\\}$ be a function and $V_{i}=\\{v\in
V(G):\;f(v)=i\\}$ for $i\in\\{0,1,2\\}$. We will identify $f$ with these
subsets of $V(G)$ induced by $f$, and write $f(V_{0},V_{1},V_{2}).$ The weight
of $f$ is defined to be

$\omega(f)=f(V(G))=\sum_{v\in V(G)}f(v)=\sum_{i}i|V_{i}|.$

Cockayne, Hedetniemi and Hedetniemi [7] defined a Roman dominating function,
abbreviated RDF, on a graph $G$ to be a function $f(V_{0},V_{1},V_{2})$
satisfying the condition that every vertex $u\in V_{0}$ is adjacent to at
least one vertex $v\in V_{2}$. The _Roman domination number_ , denoted by
$\gamma_{{}_{R}}(G)$, is the minimum weight among all RDFs on $G$, _i.e._ ,

$\gamma_{{}_{R}}(G)=\min\\{\omega(f):\,f\text{ is a RDF on }G\\}.$

A generalization of Roman domination, called Italian domination, was
introduced by Chellali et al. in [6], where it was called Roman
$\\{2\\}$-domination. The concept was studied further in [17, 18]. An Italian
dominating function, abbreviated IDF, on a graph $G$ is a function
$f(V_{0},V_{1},V_{2})$ satisfying that $f(N(v))=\sum_{u\in N(v)}f(u)\geq 2$
for every $v\in V_{0}$, i.e., $f(V_{0},V_{1},V_{2})$ is an IDF if $N(v)\cap
V_{2}\neq\varnothing$ or $|N(v)\cap V_{1}|\geq 2$ for every $v\in V_{0}$.

The _Italian domination number_ , denoted by $\gamma_{{}_{I}}(G)$, is the
minimum weight among all IDFs on $G$, _i.e._ ,

$\gamma_{{}_{I}}(G)=\min\\{\omega(f):\,f\text{ is an IDF on }G\\}.$

Given a function $f$ on $G$ and a vertex $v\in V(G)$, we can assume that
$f(v)$ is the number of entities placed in $v$. In the theory of Italian
domination, a graph $G$ is deemed protected under $f$ if every vertex of
weight zero is protected by at least two entities, i.e., if $f$ is an IDF. An
IDF of weight $\omega(f)=\gamma_{{}_{I}}(G)$ is called a
$\gamma_{{}_{I}}(G)$-function. In Section 3 we will see that for any
$\gamma_{{}_{I}}(G)$-function $f(V_{0},V_{1},V_{2})$ on $G$, the set
$D=V_{1}\cup V_{2}$ is a protector of $G$ of maximum quality, as
$\partial_{s}(D)=\partial_{s}(G)$. Furthermore, $D_{w}=V_{2}$ and
$D_{s}=V_{1}$. Therefore, in the theory of Italian domination, any
$\gamma_{{}_{I}}(G)$-function provides the minimum number of entities needed
to protect the graph and also provides a protector of maximum quality,
according to the approach described in the previous section.

We assume that the reader is familiar with the basic concepts, notation and
terminology of domination in graph. If this is not the case, we suggest the
textbooks [11, 12]. For the remainder of the paper, definitions will be
introduced whenever a concept is needed. In particular, this is the case for
concepts, notation and terminology to be used only once.

##  3 A Gallai-type theorem

In order to deduce our results, we need to state the following basic lemma.

######  Lemma 3.1.

For any graph $G$, there exists a $\partial_{s}(G)$-set which is a dominating
set of $G$.

###### Proof.

Let $D$ be a $\partial_{s}(G)$-set such that $|D|$ is maximum among all
$\partial_{s}(G)$-sets. If $D\in\mathcal{D}(G)$, then we are done. Suppose
that $D\not\in\mathcal{D}(G)$. Let $v\in V(G)\setminus D$ such that $N(v)\cap
D=\varnothing$ and let $D^{\prime}=D\cup\\{v\\}$. We differentiate two cases.

Case 1. $epn(v,D^{\prime})\neq\varnothing$. In this case,
$D^{\prime}_{w}\subseteq D_{w}\cup\\{v\\}$ and $|N(v)\setminus N[D]|\geq 1$,
which implies that $\partial_{s}(D^{\prime})\geq|N_{e}(D)|+|N(v)\setminus
N[D]|-(|D_{w}|+1)\geq|N_{e}(D)|-|D_{w}|=\partial_{s}(D)=\partial_{s}(G).$
Therefore, $D^{\prime}$ is a $\partial_{s}(G)$-set with $|D^{\prime}|>|D|$,
which is a contradiction.

Case 2. $epn(v,D^{\prime})=\varnothing$. In this case,
$D^{\prime}_{w}\subseteq D_{w}$ and $N_{e}(D^{\prime})=N_{e}(D)$, which
implies that
$\partial_{s}(D^{\prime})\geq|N_{e}(D)|-|D_{w}|=\partial_{s}(D)=\partial_{s}(G).$
As above, $D^{\prime}$ is a $\partial_{s}(G)$-set with $|D^{\prime}|>|D|$,
which is a contradiction.

According to the two cases above, $D$ is a dominating set. Therefore, the
result follows. ∎

The following straightforward remark will be one of our tools.

######  Remark 3.2.

If $D\in\mathcal{D}(G)$ is a $\partial_{s}(G)$-set, then

$\partial_{s}(G)=\operatorname{n}(G)-|D|-|D_{w}|=\operatorname{n}(G)-|D_{s}|-2|D_{w}|.$

A Gallai-type theorem has the form $a(G)+b(G)=\operatorname{n}(G)$, where
$a(G)$ and $b(G)$ are parameters defined on $G$. This terminology comes from
Theorem 2.1, which was stated in 1959 by the prolific Hungarian mathematician
Tibor Gallai.

######  Theorem 3.3 (Gallai-type theorem for the differential and the Roman
domination number, [2]).

For any graph $G$,

$\gamma_{{}_{R}}(G)+\partial(G)=\operatorname{n}(G).$

Inspired by the previous result, it is natural to ask if we are able to
establish a Gallai-type theorem involving the strong differential. Precisely,
the next result states the relationship between the strong differential and
the Italian domination number.

######  Theorem 3.4 (Gallai-type theorem for the strong differential and the
Italian domination number).

For any graph $G$,

$\gamma_{{}_{I}}(G)+\partial_{s}(G)=\operatorname{n}(G).$

###### Proof.

By Lemma 3.1, there exists a $\partial_{s}(G)$-set $D$ which is a dominating
set of $G$. Hence, the function $g(W_{0},W_{1},W_{2})$, defined from
$W_{1}=D_{s}$ and $W_{2}=D_{w}$, is an IDF on $G$, which implies that
$\gamma_{{}_{I}}(G)\leq\omega(g)=2|D_{w}|+|D_{s}|$. Therefore, Remark 3.2
leads to $\gamma_{{}_{I}}(G)\leq\operatorname{n}(G)-\partial_{s}(G).$

We proceed to show that
$\gamma_{{}_{I}}(G)\geq\operatorname{n}(G)-\partial_{s}(G).$ Let
$f(V_{0},V_{1},V_{2})$ be a $\gamma_{{}_{I}}(G)$-function. It is readily seen
that for $D^{\prime}=V_{1}\cup V_{2}$ we have that $D^{\prime}_{s}=V_{1}$ and
$D^{\prime}_{w}=V_{2}$. Thus,

$\displaystyle\partial_{s}(G)$ $\displaystyle\geq\partial_{s}(D^{\prime})$
$\displaystyle=|N_{e}(D^{\prime})|-|D^{\prime}_{w}|$
$\displaystyle=|V(G)\setminus(V_{1}\cup V_{2})|-|V_{2}|$
$\displaystyle=\operatorname{n}(G)-2|V_{2}|-|V_{1}|$
$\displaystyle=\operatorname{n}(G)-\gamma_{{}_{I}}(G).$

Therefore, the result follows. ∎

Theorem 3.4 allows us to derive results on the Italian domination number from
results on the strong differential and vice versa. In the next sections we
present some of these results.

Now we analyse the case of the computational complexity. Given a positive
integer $k$ and a graph $G$, the problem of deciding if $G$ has an Italian
dominating function $f$ of weight $\omega(f)\leq k$ is NP-complete [6]. Hence,
the problem of computing the Italian domination number of a graph is NP-hard.
Therefore, by Theorem 3.4 we immediately obtain the analogous result for the
strong differential.

######  Theorem 3.5.

The problem of computing the strong differential of a graph is $NP$-hard.

##  4 General bounds

We next present tight bounds on the strong differential of a graph. In some
cases we provide classes of graphs achieving the bounds, while in other cases
we characterize the graphs reaching the equalities.

###  4.1 Bounds in terms of the order

In this subsection, we show some interesting results on the strong
differential in terms of the order of $G$. These results are directly derived
from known results on the Italian domination number.

######  Theorem 4.1.

[18] If $G$ is a connected graph with $\operatorname{n}(G)\geq 3$, then

$\gamma_{{}_{I}}(G)\leq\frac{3}{4}\operatorname{n}(G).$

Furthermore, if $G$ is a connected graph with $\delta(G)\geq 2$, then

$\gamma_{{}_{I}}(G)\leq\frac{2}{3}\operatorname{n}(G),$

while if $\delta(G)\geq 3$, then

$\gamma_{{}_{I}}(G)\leq\frac{1}{2}\operatorname{n}(G).$

Therefore, from Theorems 3.4 and 4.1 we derive the following result on the
strong differential.

######  Theorem 4.2.

If $G$ is a connected graph with $\operatorname{n}(G)\geq 3$, then

$\partial_{s}(G)\geq\frac{1}{4}\operatorname{n}(G).$

Furthermore, if $G$ is a connected graph with $\delta(G)\geq 2$, then

$\partial_{s}(G)\geq\frac{1}{3}\operatorname{n}(G),$

while if $\delta(G)\geq 3$, then

$\partial_{s}(G)\geq\frac{1}{2}\operatorname{n}(G).$

The reader is referred to [13] for a characterization of all graphs achieving
the equalities in the bounds above.

###  4.2 Bounds in terms of order, domination number, $2$-domination number
and number of support vertices

The following results show some basic property of the Italian domination
number. Recall that a nontrivial tree is a tree of order at least $2$.

######  Theorem 4.3.

  * •

[18] If $T$ is a nontrivial tree, then $\gamma_{{}_{I}}(T)\geq\gamma(T)+1.$

  * •

[6] For every graph $G$, $\gamma_{{}_{I}}(G)\leq\gamma_{{}_{R}}(G)\leq
2\gamma(G).$

  * •

[6] For every graph $G$, $\gamma_{{}_{I}}(G)\leq\gamma_{{}_{2}}(G).$

The trees satisfying $\gamma_{{}_{I}}(T)=\gamma(T)+1$, and the trees
satisfying $\gamma_{{}_{I}}(T)=2\gamma(T)$, were characterized in [17].

From Theorems 3.4 and 4.3 we conclude that if $T$ is a nontrivial tree, then
$\partial_{s}(T)\leq n(T)-\gamma(T)-1.$ As the next result shows, we can state
a more general bound, which improves the previous one for some classes of
trees. Here $\sigma(G)$ denotes the number of support vertices of $G$ which
are adjacent to more than one leaf.

######  Theorem 4.4.

For any graph $G$,

$\operatorname{n}(G)-\min\\{2\gamma(G),\gamma_{{}_{2}}(G)\\}\leq\partial_{s}(G)\leq\operatorname{n}(G)-\gamma(G)-\sigma(G).$

###### Proof.

By Lemma 3.1, there exists $D\in\mathcal{D}(G)$ which is a
$\partial_{s}(G)$-set. For every $x\in\mathcal{S}(G)$ we define
$\mathcal{L}(x)=N(x)\cap\mathcal{L}(G)$ and
$\mathcal{L}[x]=\\{x\\}\cup\mathcal{L}(x)$. Let
$\mathcal{S}^{\prime}(G)=\\{x\in\mathcal{S}(G):\,|\mathcal{L}(x)|\geq 2\\}$
and $D^{\prime}=\mathcal{S}^{\prime}(G)\cup
D\setminus(\cup_{x\in\mathcal{S}^{\prime}(G)}\mathcal{L}(x))$. Notice that
$D^{\prime}$ is a dominating set of $G$ and for any
$x\in\mathcal{S}^{\prime}(G)$, either $|D\cap\mathcal{L}[x]|=1$ and $x\in
D_{w}$ or $|D\cap\mathcal{L}[x]|\geq 2$, while
$|D^{\prime}\cap\mathcal{L}[x]|=1$ and $x\in D^{\prime}_{w}$. Hence,
$\gamma(G)\leq|D^{\prime}|\leq|D|$, $\sigma(G)\leq|D^{\prime}_{w}|$ and
$|D^{\prime}|+|D^{\prime}_{w}|\leq|D|+|D_{w}|$. Therefore, by Remark 3.2,

$\partial_{s}(G)=\operatorname{n}(G)-|D|-|D_{w}|\leq\operatorname{n}(G)-|D^{\prime}|-|D^{\prime}_{w}|\leq\operatorname{n}(G)-\gamma(G)-\sigma(G).$

Finally, the lower bounds are derived from Theorems 3.4 and 4.3. ∎

We next present some classes of graphs for which the bounds above are
achieved. To begin with, we consider the following result, which is an
immediate consequence of Theorem 4.4.

######  Corollary 4.5.

Let $G$ be a graph. If $\gamma_{{}_{2}}(G)=\gamma(G)$, then
$\partial_{s}(G)=\operatorname{n}(G)-\gamma_{{}_{2}}(G)$.

Figure 2: The set of (gray and black) coloured vertices forms a
$\partial_{s}(G)$-set and a $\gamma_{{}_{2}}(G)$-set, while the set of black-
coloured vertices forms a $\gamma(G)$-set.

The converse of Corollary 4.5 does not hold. For instance, for the graph $G$
shown in Figure 2 we have that
$\partial_{s}(G)=4=\operatorname{n}(G)-\gamma_{{}_{2}}(G)$, while
$\gamma_{{}_{2}}(G)=4>2=\gamma(G)$.

Now, if $\mathcal{G}$ is the family of graphs of order at least three, where
$\\{\mathcal{L}(G),\mathcal{S}(G)\\}$ is a partition of $V(G)$ and every
support vertex is adjacent to at least two leaves, then for every
$G\in\mathcal{G}$ we have that $\gamma(G)=|\mathcal{S}(G)|=\sigma(G)$. In such
a case, the only $\gamma(G)$-set is $\mathcal{S}(G)$, and we have that
$\partial_{s}(G)\geq\partial_{s}(S)=|\mathcal{L}(G)|-|\mathcal{S}(G)|=\operatorname{n}(G)-2\gamma(G)$.
Therefore, Theorem 4.4 leads to the following remark.

######  Remark 4.6.

If $G\in\mathcal{G}$, then
$\partial_{s}(G)=\partial(G)=\operatorname{n}(G)-2\gamma(G)=\operatorname{n}(G)-\gamma(G)-\sigma(G)$.

Next we proceed to discuss the case of graphs with
$\partial_{s}(G)=\operatorname{n}(G)-\gamma(G)$.

######  Proposition 4.7.

Given a graph $G$, the following statements are equivalent.

  1. (i)

$\partial_{s}(G)=\operatorname{n}(G)-\gamma(G)$.

  2. (ii)

$\gamma_{{}_{2}}(G)=\gamma(G)$.

###### Proof.

First, assume $\partial_{s}(G)=\operatorname{n}(G)-\gamma(G)$. By Lemma 3.1,
there exists $D\in\mathcal{D}(G)$ which is a $\partial_{s}(G)$-set. Since
$\gamma(G)\leq|D|$, Remark 3.2 leads to
$\partial_{s}(G)=\operatorname{n}(G)-|D|-|D_{w}|\leq\operatorname{n}(G)-\gamma(G).$
Hence, $|D|=\gamma(G)$ and $|D_{w}|=0$, which implies that $D=D_{s}$ and so
$D$ is also a $2$-dominating set of $G$. Therefore,
$\gamma_{{}_{2}}(G)\leq|D|=\gamma(G)\leq\gamma_{{}_{2}}(G)$, which leads to
$\gamma_{{}_{2}}(G)=\gamma(G)$.

Conversely, if $\gamma_{{}_{2}}(G)=\gamma(G)$, then Theorem 4.4 leads to
$\partial_{s}(G)=\operatorname{n}(G)-\gamma(G)$, which completes the proof. ∎

Our next result describes the structure of some particular
$\partial_{s}(G)$-sets for graphs with
$\partial_{s}(G)=\operatorname{n}(G)-\gamma_{{}_{2}}(G)$.

######  Proposition 4.8.

Given a graph $G$, the following statements are equivalent.

  1. (i)

$\partial_{s}(G)=\operatorname{n}(G)-\gamma_{{}_{2}}(G)$.

  2. (ii)

There exists a $\partial_{s}(G)$-set $D$ which is a dominating set and
$D_{w}=\varnothing$.

###### Proof.

If there exists a $\partial_{s}(G)$-set $D$ which is a dominating set with
$D_{w}=\varnothing$, then $D$ is a $2$-dominating set. Hence,
$\partial_{s}(G)=\partial_{s}(D)=|N_{e}(D)|=\operatorname{n}(G)-|D|\leq\operatorname{n}(G)-\gamma_{{}_{2}}(G)$.
By Theorem 4.4 we deduce that
$\partial_{s}(G)=\operatorname{n}(G)-\gamma_{{}_{2}}(G)$.

Conversely, assume $\partial_{s}(G)=\operatorname{n}(G)-\gamma_{{}_{2}}(G)$.
For any $\gamma_{{}_{2}}(G)$-set $X$ we have that $X_{w}=\varnothing$, and so
$\partial_{s}(G)=\operatorname{n}(G)-\gamma_{{}_{2}}(G)=|N_{e}(X)|=|N_{e}(X)|-|X_{w}|=\partial_{s}(X)$.
This implies that $X$ is a $\partial_{s}(G)$-set satisfying the required
conditions, which completes the proof. ∎

Next we consider the case of graphs with
$\partial_{s}(G)=\operatorname{n}(G)-\gamma_{{}_{2}}(G)$.

######  Proposition 4.9.

Given a graph $G$, the following statements are equivalent.

  1. (i)

$\partial_{s}(G)=\operatorname{n}(G)-2\gamma(G)$.

  2. (ii)

Every $\gamma(G)$-set $D$ is a $\partial_{s}(G)$-set with $D_{s}=\varnothing$.

###### Proof.

First, assume $\partial_{s}(G)=\operatorname{n}(G)-2\gamma(G)$, and let $D$ be
a $\gamma(G)$-set. Since $|N_{e}(D)|=\operatorname{n}(G)-\gamma(G)$, we have
that
$\operatorname{n}(G)-2\gamma(G)+|D_{s}|=|N_{e}(D)|-|D|+|D_{s}|=\partial_{s}(D)\leq\partial_{s}(G)=\operatorname{n}(G)-2\gamma(G),$
which implies that $D_{s}=\varnothing$ and $\partial_{s}(D)=\partial_{s}(G)$.

Conversely, if very $\gamma(G)$-set $D$ is a $\partial_{s}(G)$-set and
$D_{s}=\varnothing$, then
$\partial_{s}(G)=\partial_{s}(D)=|N_{e}(D)|-|D|=\operatorname{n}(G)-2\gamma(G)$.
∎

By Theorem 4.4 and Proposition 4.9 we deduce the following result.

######  Proposition 4.10.

If there exists a $\gamma(G)$-set $D$ such that $D_{s}\neq\varnothing$, then

$\partial_{s}(G)\geq\operatorname{n}(G)-2\gamma(G)+1.$

The bound above is tight. For instance, it is achieved by any graph $G$ of
order $r+2$ obtained from a star $K_{1,r}$ by subdividing one edge. In such a
case, $\partial_{s}(G)=r-1=\operatorname{n}(G)-2\gamma(G)+1.$

######  Theorem 4.11.

Let $G$ be a graph. If $\delta(G)\geq 2$, then

$\partial_{s}(G)\geq\frac{1}{2}\left(\operatorname{n}(G)-\gamma(G)\right).$

###### Proof.

Let $S$ be a $\gamma(G)$-set and $C\subseteq V(G)\setminus S$ the set of
isolated vertices of the graph $G[V(G)\setminus S]$. Assume $\delta(G)\geq 2$.
If $V(G)=S\cup C$, then $S_{w}=\varnothing$ and so

$\partial_{s}(G)\geq\partial_{s}(S)=|N_{e}(S)|=\operatorname{n}(G)-\gamma(G)\geq\frac{1}{2}(\operatorname{n}(G)-\gamma(G)).$

Now, assume $V(G)\setminus(S\cup C)\neq\varnothing$. Let $S^{\prime}$ be a
$\gamma(G[V(G)\setminus(S\cup C)])$-set. Since $G[V(G)\setminus(S\cup C)]$
does not have isolated vertices,
$|S^{\prime}|\leq\frac{1}{2}(\operatorname{n}(G)-(|S|+|C|))\leq\frac{1}{2}(\operatorname{n}(G)-\gamma(G))$.
Let $D=S\cup S^{\prime}$. Notice that $D$ is a dominating set of $G$ and
$D_{w}=\varnothing$. Hence,

$\displaystyle\partial_{s}(G)$ $\displaystyle\geq\partial_{s}(D)$
$\displaystyle=|N_{e}(D)|$ $\displaystyle=\operatorname{n}(G)-|D|$
$\displaystyle\geq\operatorname{n}(G)-\left(\gamma(G)+\frac{1}{2}(\operatorname{n}(G)-\gamma(G))\right)$
$\displaystyle=\frac{1}{2}(\operatorname{n}(G)-\gamma(G)).$

Therefore, the result follows. ∎

In order to show a class of graphs with
$\partial_{s}(G)=\frac{1}{2}(\operatorname{n}(G)-\gamma(G))$, we consider the
case of corona graphs. Given two graphs $G_{1}$ and $G_{2}$, the corona
product graph $G_{1}\odot G_{2}$ is the graph obtained from $G_{1}$ and
$G_{2}$, by taking one copy of $G_{1}$ and $\operatorname{n}(G_{1})$ copies of
$G_{2}$ and joining by an edge every vertex from the $i^{th}$-copy of $G_{2}$
with the $i^{th}$-vertex of $G_{1}$. For every $x\in V(G_{1})$, the copy of
$G_{2}$ in $G_{1}\odot G_{2}$ associated to $x$ will be denoted by $G_{2,x}$.
The following result was presented without proof in [4]. The reader is
referred to [5] for a detailed proof.

######  Proposition 4.12.

[4] For any graph $G_{1}$ and any nontrivial graph $G_{2}$,

$\partial(G_{1}\odot
G_{2})=\operatorname{n}(G_{1})(\operatorname{n}(G_{2})-1).$

From the previous result we can easily deduce the following proposition.

######  Proposition 4.13.

For any graph $G_{1}$ and any nontrivial graph $G_{2}$,

$\partial_{s}(G_{1}\odot
G_{2})=\operatorname{n}(G_{1})(\operatorname{n}(G_{2})-1).$

###### Proof.

By Theorem 4.14 and Proposition 4.12 we deduce that

$\partial_{s}(G_{1}\odot
G_{2})\geq\operatorname{n}(G_{1})(\operatorname{n}(G_{2})-1).$

Now, let $S$ be a $\partial_{s}(G_{1}\odot G_{2})$-set and $S^{\prime}=\\{x\in
V(G_{1}):\,S\cap(\\{x\\}\cup V(G_{2,x}))\neq\varnothing\\}$. Thus,

$\partial_{s}(G_{1}\odot
G_{2})=|N_{e}(S)|-|S_{w}|\leq(\operatorname{n}(G_{1})-|S^{\prime}|)+\sum_{x\in
S^{\prime}}(\operatorname{n}(G_{2})-1)\leq\operatorname{n}(G_{1})(\operatorname{n}(G_{2})-1).$

Therefore, the result follows. ∎

The bound given in Theorem 4.11 is achieved by any corona graph of the form
$G\cong G_{1}\odot K_{2}$, where $G_{1}$ is an arbitrary graph. In this case,
$\gamma(G)=\operatorname{n}(G_{1})$, so that
$\partial_{s}(G)=\operatorname{n}(G_{1})=\frac{1}{2}(\operatorname{n}(G)-\gamma(G)).$

###  4.3 Bounds in terms of domination number and differential

######  Theorem 4.14.

For any graph $G$,

$\partial(G)\leq\partial_{s}(G)\leq\partial(G)+\gamma(G)-1.$

###### Proof.

It is well known that for every graph $G$,

$\partial(G)\geq\operatorname{n}(G)-2\gamma(G).$ (1)

From Theorem 4.4 and Eq. (1) we have that
$\partial_{s}(G)\leq\operatorname{n}(G)-\gamma(G)\leq\partial(G)+\gamma(G)$.
Now, if $\partial_{s}(G)=\partial(G)+\gamma(G)$, then
$\partial(G)=\operatorname{n}(G)-2\gamma(G)$ and
$\partial_{s}(G)=\operatorname{n}(G)-\gamma(G)$. Hence, by Proposition 4.7,
$\gamma_{2}(G)=\gamma(G)$. Thus, any $\gamma_{{}_{2}}(G)$-set $S$ is an
independent set, and so for any $v\in S$, we have that
$N_{e}(S\setminus\\{v\\})=V(G)\setminus S$. This implies that

$\partial(G)\geq\partial(S\setminus\\{v\\})=|N_{e}(S\setminus\\{v\\})|-|(S\setminus\\{v\\})|=\operatorname{n}(G)-2\gamma(G)+1,$

which is a contradiction. Therefore,
$\partial_{s}(G)\leq\partial(G)+\gamma(G)-1$.

On the other side, for any $\partial(G)$-set $D$,

$\partial(G)=\partial(D)=|N_{e}(D)|-|D|\leq|N_{e}(D)|-|D_{w}|=\partial_{s}(D)\leq\partial_{s}(G).$

Therefore, the result follows. ∎

The upper bound $\partial_{s}(G)\leq\partial(G)+\gamma(G)-1$ is tight. For
instance, it is achieved by the complete bipartite graph $K_{2,r}$.

Next we proceed to discuss the structure of some particular
$\partial_{s}(G)$-sets for graphs with $\partial_{s}(G)=\partial(G)$.

######  Proposition 4.15.

Given a graph $G$, the following statements are equivalent.

  1. (i)

$\partial_{s}(G)=\partial(G)$.

  2. (ii)

There exists a $\partial_{s}(G)$-set $D$ such that $D_{s}=\varnothing$.

###### Proof.

If there exists a $\partial_{s}(G)$-set $D$ with $D_{w}=D$, then

$\partial_{s}(G)=\partial_{s}(D)=|N_{e}(D)|-|D_{w}|=|N_{e}(D)|-|D|=\partial(D)\leq\partial(G).$

Hence, Theorem 4.14 leads to $\partial_{s}(G)=\partial(G)$.

Conversely, assume $\partial_{s}(G)=\partial(G)$. If $D^{\prime}$ is a
$\partial(G)$-set, then

$|N_{e}(D^{\prime})|-|D^{\prime}_{w}|=\partial_{s}(D^{\prime})\leq\partial_{s}(G)=\partial(G)=|N_{e}(D^{\prime})|-|D^{\prime}|\leq|N_{e}(D^{\prime})|-|D^{\prime}_{w}|,$

and since $D^{\prime}_{w}\subseteq D^{\prime}$, we conclude that
$D^{\prime}=D^{\prime}_{w}$ and also $D^{\prime}$ is a $\partial_{s}(G)$-set,
which completes the proof. ∎

To conclude this subsection we proceed to derive a result for the particular
case of trees. To this end, we need to recall the following known result.

######  Theorem 4.16.

[6] For any tree $T$,

$\gamma_{{}_{I}}(T)\geq\frac{3}{4}\gamma_{{}_{R}}(T).$

The following bound is a direct consequence of Theorems 3.4 and 4.16.

######  Theorem 4.17.

For any tree $T$,

$\partial_{s}(T)\leq\left\lfloor\frac{\operatorname{n}(T)+3\partial(T)}{4}\right\rfloor.$

The bound above is tight. For instance, it is achieved by any path of order
$6k+3$, as $\partial_{s}(P_{6k+3})=3k+1$ and $\partial(P_{6k+3})=2k+1$, which
implies that
$\partial_{s}(P_{6k+3})=\left\lfloor\frac{6k+3+3\partial(P_{6k+3})}{4}\right\rfloor$.

###  4.4 Bounds in terms of order and maximum degree

Next we present another basic result obtained in [6].

######  Theorem 4.18.

[6] For any connected graph $G$,
$\gamma_{{}_{I}}(G)\geq\frac{2\operatorname{n}(G)}{\Delta(G)+2}$.

It is not difficult to observe that the result above works for non-connected
graphs.

######  Theorem 4.19.

For any graph $G$,

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

###### Proof.

To prove the lower bound we only need to observe that for every vertex $v$ of
maximum degree, $\partial_{s}(G)\geq\partial_{s}(\\{v\\})=\Delta(G)-1$.

The upper bound is a direct consequence of Theorems 3.4 and 4.18. ∎

It is well known that
$\gamma_{{}_{2}}(G)\geq\frac{2\operatorname{n}(G)}{\Delta(G)+2}$ for every
graph $G$. The next result shows that the case
$\gamma_{{}_{2}}(G)=\frac{2\operatorname{n}(G)}{\Delta(G)+2}$ characterises
the graphs with
$\partial_{s}(G)=\frac{\operatorname{n}(G)\Delta(G)}{\Delta(G)+2}$.
Consequently, these graphs satisfy
$\partial_{s}(G)=\operatorname{n}(G)-\gamma_{{}_{2}}(G)$.

######  Proposition 4.20.

Given a graph $G$, the following statements are equivalent.

  1. (i)

$\partial_{s}(G)=\frac{\operatorname{n}(G)\Delta(G)}{\Delta(G)+2}$.

  2. (ii)

$\gamma_{{}_{2}}(G)=\frac{2\operatorname{n}(G)}{\Delta(G)+2}$.

###### Proof.

If $\gamma_{{}_{2}}(G)=\frac{2\operatorname{n}(G)}{\Delta(G)+2}$, then
Theorems 4.4 and 4.19 immediately lead to
$\partial_{s}(G)=\frac{\operatorname{n}(G)\Delta(G)}{\Delta(G)+2}$.

In order to prove the converse, let $D$ be a $\partial_{s}(G)$-set which
satisfies Lemma 3.1. Let $X=\cup_{v\in D_{w}}\operatorname{epn}(v,D)$. Notice
that $|X|\leq\Delta(G)|D_{w}|$. Moreover, since every vertex $v\in
N_{e}(D)\setminus X$ satisfies that $|N(v)\cap D_{s}|\geq 2$, we obtain that
$2|N_{e}(D)\setminus X|\leq\Delta(G)|D_{s}|$. Hence, since
$D\in\mathcal{D}(G)$,

$\displaystyle\operatorname{n}(G)=$ $\displaystyle|D|+|N_{e}(D)|$
$\displaystyle\leq$
$\displaystyle|D_{w}|+|D_{s}|+\Delta(G)|D_{w}|+\frac{1}{2}\Delta(G)|D_{s}|$
$\displaystyle\leq$
$\displaystyle(\Delta(G)+1)|D_{w}|+\frac{1}{2}(\Delta(G)+2)|D_{s}|$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}(\Delta(G)+2)(2|D_{w}|+|D_{s}|)$
$\displaystyle=$
$\displaystyle\frac{1}{2}(\Delta(G)+2)(\operatorname{n}(G)-\partial_{s}(G)).$

Thus, if $\partial_{s}(G)=\frac{\operatorname{n}(G)\Delta(G)}{\Delta(G)+2}$,
then we have equalities in the previous inequality chain, which implies that
$D_{w}=\varnothing$. Therefore, by Proposition 4.8,
$\frac{\operatorname{n}(G)\Delta(G)}{\Delta(G)+2}=\partial_{s}(G)=\operatorname{n}(G)-\gamma_{{}_{2}}(G)$,
which implies that
$\gamma_{{}_{2}}(G)=\frac{2\operatorname{n}(G)}{\Delta(G)+2}$. ∎

To conclude this subsection we characterize the trees for which the bound
$\partial_{s}(G)\geq\Delta(G)-1$ is achieved. To this end, we need to
introduce some additional notation.

Given a tree $T$ and $v\in V(T)$, the eccentricity of $v$ is denoted by
$ecc(v)$. We also define the following sets associated to $v$,

$\mathcal{L}(v)=N(v)\cap\mathcal{L}(T)\,\,\text{ and
}\,\,\mathcal{S}_{2}(v)=\\{u\in N(v):\,\deg(u)=2\\}.$

We say that a tree $T$ belongs to the family $\mathcal{T}$ if the following
conditions hold for every vertex $v\in V(T)$ with $\deg(v)=\Delta(T)$.

  * A.1:

$v\in\mathcal{S}(T)$ and $ecc(v)\leq 3$.

  * A.2:

$\deg(u)\leq 3$ and $|\mathcal{S}_{2}(u)|\leq 1$ for every $u\in N(v)$.

  * A.3:

$\deg(u)\leq 2$ for every $u\in V(T)\setminus N[v]$.

  * A.4:

$|\mathcal{L}(v)|\geq 2$ or there exists $u\in N(v)\cap\mathcal{S}(T)$ such
that $\deg(u)=2$.

######  Lemma 4.21.

Let $T\in\mathcal{T}$ and $v\in V(T)$. If $\deg(v)=\Delta(T)$, then there
exists a $\partial_{s}(T)$-set $D$ such that $v\in D_{w}$.

###### Proof.

Suppose to the contrary that $v\notin D_{w}$ for every $\partial_{s}(T)$-set
$D$. Let us fix a $\partial_{s}(T)$-set $D$. Notice that $v\in\mathcal{S}(T)$,
by A.1. If $|\mathcal{L}(v)|\geq 2$, then
$\partial_{s}(\\{v\\}\cup(D\setminus\mathcal{L}(v))\geq\partial_{s}(D)$, which
is a contradiction. Now, if $|\mathcal{L}(v)|=1$, then by A.4 there exists
$u\in N(v)\cap\mathcal{S}(T)$ such that $\deg(u)=2$. So, for
$X=\\{v\\}\cup\mathcal{L}(u)\cup D\setminus(\mathcal{L}(v)\cup\\{u\\})$ we
have that $\partial_{s}(X)\geq\partial_{s}(D)$, which is again a
contradiction, as $X$ is a $\partial_{s}(T)$-set and $v\in X_{w}$. Therefore,
the result follows. ∎

######  Proposition 4.22.

Let $T$ be a tree with $\operatorname{n}(T)\geq 3$. Then
$\partial_{s}(T)=\Delta(T)-1$ if and only if $T\in\mathcal{T}$.

###### Proof.

Assume $\partial_{s}(T)=\Delta(T)-1$ and let $v\in V(T)$ with
$\deg(v)=\Delta(T)$. First, we proceed to prove that A.1 holds. If
$v\not\in\mathcal{S}(T)$, then $\partial_{s}(T)\geq\partial_{s}(V(T)\setminus
N(v))=\Delta(T)$, which is a contradiction. Hence, $v\in\mathcal{S}(T)$. Now,
if $ecc(v)\geq 4$, then there exists a vertex $v^{\prime}\in V(T)$, which is
at distance three from $v$, such that $\deg(v^{\prime})\geq 2$. Notice that
$\partial_{s}(\\{v,v^{\prime}\\})\geq\Delta(T)$, which is again a
contradiction. Hence, $ecc(v)\leq 3$, as desired.

Now, we proceed to prove that A.2 holds. Suppose that there exists $u\in N(v)$
such that $\deg(u)\geq 4$. In this case,
$\partial_{s}(\\{v,u\\})\geq\Delta(T)$, which is a contradiction. Now, if
there exists $u\in N(v)$ such that $|\mathcal{S}_{2}(u)|\geq 2$, then
$\partial_{s}(\\{v\\}\cup N(\mathcal{S}_{2}(u)))\geq\Delta(T)$, which is a
contradiction. Therefore, A.2 follows.

From A.1 and A.2, if $T$ is a path, then $T\cong P_{3}$ or $T\cong P_{4}$.
Hence, from now on we assume that $\Delta(T)\geq 3$.

Now, if there exists $u\in V(T)\setminus N[v]$ such that $\deg(u)\geq 3$, then
$\partial_{s}(\\{v,u\\})\geq\Delta(T)$, which is a contradiction. Therefore,
A.3 follows.

Finally, we proceed to prove that A.4 holds. Suppose to the contrary that
$|\mathcal{L}(v)|=1$ and for every $u\in N(v)\setminus\mathcal{L}(v)$ either
$\mathcal{S}_{2}(u)\neq\varnothing$ or $\mathcal{S}_{2}(u)=\varnothing$ and
$\deg(u)=3$. Let $U^{\prime}=\\{u\in
N(v):\,\mathcal{S}_{2}(u)\neq\varnothing\\}$ and
$U^{\prime\prime}=N(v)\setminus(U^{\prime}\cup\mathcal{L}(v))$. Notice that if
$u\in U^{\prime}$, then $|\mathcal{S}_{2}(u)|=1$ and $|\mathcal{L}(u)|\leq 1$,
by A.2. Also, if $u\in U^{\prime\prime}$, then $|\mathcal{L}(u)|=2$. Now, let
$X=X^{\prime}\cup U^{\prime\prime}$, where

$X^{\prime}=\mathcal{L}(v)\cup\left(\bigcup_{u\in
U^{\prime}}(\\{u\\}\cup\mathcal{S}_{2}(u)\cup\mathcal{L}(u))\right).$

Since $X_{s}=X^{\prime}$ and $X_{w}=U^{\prime\prime}$, we have that
$\partial_{s}(X)=|N_{e}(X)|-|X_{w}|=(1+|X^{\prime}|+2|U^{\prime\prime}|)-|U^{\prime\prime}|=1+|X^{\prime}|+|U^{\prime\prime}|=\Delta(v)$,
which is a contradiction. Therefore, A.4 follows.

Conversely, assume that $T\in\mathcal{T}$. By Theorem 4.19, we only need to
prove that $\partial_{s}(T)\leq\Delta(T)-1$. As above, let $v\in V(T)$ with
$\deg(v)=\Delta(T)$. By Lemma 4.21, there exists $\partial_{s}(T)$-set $D$
such that $v\in D_{w}$. We take $D$ of minimum cardinality among these sets.
Now, if $N(v)\cap D=\varnothing$, then A.1 and A.3 lead to $|N(x)\cap D|\leq
1$ for every $x\in V(T)\setminus N[v]$, which implies that
$\partial_{s}(T)=\partial_{s}(D)\leq\partial_{s}(\\{v\\})=\Delta(T)-1$. Now,
suppose to the contrary that there exists $v^{\prime}\in N(v)\cap D$. Let
$T_{v^{\prime}}$ be the sub-tree of $T$ with root $v^{\prime}$ obtained from
$T$ by removing the edge $\\{v,v^{\prime}\\}$. By A.2 we have that
$\deg(v^{\prime})\leq 3$ and $|\mathcal{S}_{2}(v^{\prime})|\leq 1$. Now, if
$\deg(v^{\prime})\leq 2$, then by A.1 either $T_{v^{\prime}}$ is a trivial
tree or $T_{v^{\prime}}\cong P_{2}$. Hence,
$\partial_{s}(T)=\partial_{s}(D)<\partial_{s}(D\setminus(\\{v^{\prime}\\}\cup\mathcal{L}(v^{\prime})))$,
which is a contradiction. Finally, if $\deg(v^{\prime})=3$, then either
$T_{v^{\prime}}\cong P_{3}$ or $T_{v^{\prime}}\cong P_{4}$, and so
$\partial_{s}(T)=\partial_{s}(D)\leq\partial_{s}(D\setminus
V(T_{v^{\prime}}))$, which is a contradiction, as $|D|>|D\setminus
V(T_{v^{\prime}})|$. Therefore, the result follows. ∎

###  4.5 Bounds in terms of vertex cover number and independence number

If $G$ is a graph with $\delta(G)\geq 2$, then any vertex cover $S$ is a
$2$-dominating set, as $V(G)\setminus S$ is an independent set. Hence,
$\delta(G)\geq 2$ leads to
$\operatorname{n}(G)-\gamma_{{}_{2}}(G)\geq\operatorname{n}(G)-\beta(G)=\alpha(G)$.
Therefore, the following result is a direct consequence of Theorem 4.4.

######  Corollary 4.23.

If $G$ is a graph with $\delta(G)\geq 2$, then $\partial_{s}(G)\geq\alpha(G)$.

The bound above is tight. For instance, the graph $G$ shown in Figure 2
satisfies $\partial_{s}(G)=4=\alpha(G)$.

The following result, which states that
$\partial_{s}(G)\geq\frac{1}{2}(\operatorname{n}(G)-\alpha(G))=\frac{1}{2}\beta(G),$
is not restricted to the case of graphs with $\delta(G)\geq 2$.

######  Theorem 4.24.

Let $G$ be a graph. If every component of $G$ has maximum degree at least two,
then

$\partial_{s}(G)\geq\frac{1}{2}\beta(G).$

###### Proof.

Assume that every component of $G$ has maximum degree at least two. Let $S$ be
an $\alpha(G)$-set containing all leaves. Let $C\subseteq V(G)\setminus S$ be
the set of isolated vertices of $G[V(G)\setminus S]$. If $V(G)=S\cup C$, then

$\partial_{s}(G)\geq\partial_{s}(S)=|N_{e}(S)|-|S_{w}|=\operatorname{n}(G)-\alpha(G)\geq\frac{1}{2}(\operatorname{n}(G)-\alpha(G))=\frac{1}{2}\beta(G).$

Assume $V(G)\setminus(S\cup C)\neq\varnothing$. Let $S^{\prime}$ be a
$\gamma(G[V(G)\setminus(S\cup C)])$-set. Since the subgraph
$G[V(G)\setminus(S\cup C)]$ does not have isolated vertices,

$|S^{\prime}|\leq\frac{1}{2}(\operatorname{n}(G)-(|S|+|C|))\leq\frac{1}{2}(\operatorname{n}(G)-\alpha(G)).$

Now, let $D=S\cup S^{\prime}$. Notice that $D$ is a dominating set of $G$ and
$D_{w}=\varnothing$. Hence,

$\displaystyle\partial_{s}(G)$ $\displaystyle\geq\partial_{s}(D)$
$\displaystyle=|N_{e}(D)|$ $\displaystyle=\operatorname{n}(G)-|D|$
$\displaystyle\geq\operatorname{n}(G)-\left(\alpha(G)+\frac{1}{2}(\operatorname{n}(G)-\alpha(G))\right)$
$\displaystyle=\frac{1}{2}(\operatorname{n}(G)-\alpha(G))$
$\displaystyle=\frac{1}{2}\beta(G).$

Therefore, the result follows. ∎

The bound given in Theorem 4.24 is achieved by any corona graph of the form
$G\cong G_{1}\odot K_{2}$, where $G_{1}$ is an arbitrary graph. In this case,
$\beta(G)=2\operatorname{n}(G_{1})$ and $\alpha(G)=\operatorname{n}(G_{1})$,
so that
$\partial_{s}(G)=\operatorname{n}(G_{1})=\frac{1}{2}\beta(G)=\frac{1}{2}(\operatorname{n}(G)-\alpha(G)).$

###  4.6 Bounds in terms of order and semitotal domination number

A semitotal dominating set of a graph $G$ without isolated vertices, is a
dominating set $D$ of $G$ such that every vertex in $D$ is within distance two
of another vertex of $D$. The semitotal domination number, denoted by
$\gamma_{{}_{t2}}(G)$, is the minimum cardinality among all semitotal
dominating sets of $G$. This parameter was introduced by Goddard et al. in
[10], and it was also studied in [14, 15, 16].

Since every semitotal dominating set is also a dominating set, and every
$2$-dominating set is a semitotal dominating set, the next inequality chain
holds.

$\gamma(G)\leq\gamma_{{}_{t2}}(G)\leq\gamma_{{}_{2}}(G).$ (2)

The following result improves the upper bound given in Theorem 4.4 for graphs
without isolated vertices.

######  Theorem 4.25.

For any graph without isolated vertices,

$\partial_{s}(G)\leq\operatorname{n}(G)-\gamma_{{}_{t2}}(G).$

###### Proof.

By Lemma 3.1, there exists $D\in\mathcal{D}(G)$ which is a
$\partial_{s}(G)$-set. We consider a set $X\subseteq V(G)$ of minimum
cardinality among the sets satisfying that $D\subseteq X$ and for any $x\in
D_{w}$, there exists $u\in N(x)\cap X$. Since $D$ is a dominating set of $G$,
it is readily seen that $X$ is a semitotal dominating set and also
$|X|\leq|D_{s}|+2|D_{w}|$. Hence, Remark 3.2 leads to

$\partial_{s}(G)=\operatorname{n}(G)-(|D_{s}|+2|D_{w}|)\leq\operatorname{n}(G)-|X|\leq\operatorname{n}(G)-\gamma_{{}_{t2}}(G).$

∎

The bound above is achieved by the graph shown in Figure1. In this case,
$\gamma_{{}_{t2}}(G)=6$ and
$\partial_{s}(G)=\operatorname{n}(G)-\gamma_{{}_{t2}}(G)=8$.

The following result is an immediate consequence of Theorems 4.4 and 4.25.

######  Proposition 4.26.

Let $G$ be a graph. If $\gamma_{{}_{t2}}(G)=\gamma_{{}_{2}}(G)$, then
$\partial_{s}(G)=\operatorname{n}(G)-\gamma_{{}_{2}}(G)$.

The converse of Proposition 4.26 does not hold. For instance, for the graph
$G$ shown in Figure 2 we have that
$\partial_{s}(G)=4=\operatorname{n}(G)-\gamma_{{}_{2}}(G)$, while
$\gamma_{{}_{2}}(G)=4>2=\gamma_{{}_{t2}}(G)$.

###  4.7 Trivial bounds and extreme cases

In this subsection we discuss the trivial bounds on $\partial_{s}(G)$ and we
characterize the extreme cases.

######  Proposition 4.27.

Given a graph $G$ of order $\operatorname{n}(G)\geq 3$, the following
statements hold.

  1. (i)

$0\leq\partial_{s}(G)\leq\operatorname{n}(G)-2.$

  2. (ii)

$\partial_{s}(G)=0$ if and only if $\Delta(G)\leq 1$.

  3. (iii)

$\partial_{s}(G)=1$ if and only if either $G\cong G_{1}$ or $G\cong G_{1}\cup
G_{2}$, where $G_{1}\in\\{C_{3},P_{3},P_{4}\\}$ and $\Delta(G_{2})\leq 1$.

  4. (iv)

$\partial_{s}(G)=\operatorname{n}(G)-2$ if and only if
$\Delta(G)=\operatorname{n}(G)-1$ or $\gamma_{{}_{2}}(G)=2$.

  5. (v)

$\partial_{s}(G)=\operatorname{n}(G)-3$ if and only if $\gamma_{{}_{2}}(G)=3$
and $\Delta(G)\leq\operatorname{n}(G)-2$ or $\gamma_{{}_{2}}(G)>3$ and
$\Delta(G)=\operatorname{n}(G)-2$.

###### Proof.

Since $\partial_{s}(\varnothing)=0$, we have that $\partial_{s}(G)\geq 0$. To
prove the remaining statements, we take a $\partial_{s}(G)$-set
$D\in\mathcal{D}(G)$, which exists due to Lemma 3.1. Now, since $|D|\geq 1$,
either $|N_{e}(D)|\leq\operatorname{n}(G)-2$ or $|D_{w}|\geq 1$, which implies
that $\partial_{s}(G)=\partial_{s}(D)\leq\operatorname{n}(G)-2$.

We proceed to prove (ii). If $\Delta(G)\leq 1$, then $|N_{e}(D)|\leq|D_{w}|$.
This implies that $\partial_{s}(G)=\partial_{s}(D)=0$. Conversely, if
$\partial_{s}(G)=0$, then
$\deg(v)-1=\partial_{s}(\\{v\\})\leq\partial_{s}(G)=0$ for every $v\in V(G)$,
which implies that $\Delta(G)\leq 1$. Therefore, (ii) follows.

We next proceed to prove (iii). If $\partial_{s}(G)=1$, then (i) and (ii) lead
to $\Delta(G)=2$. If $G$ is connected, then it is easy to see that
$G\in\\{C_{3},P_{3},P_{4}\\}$. If $G$ is not connected, then by (ii) we deduce
that $G\cong G_{1}\cup G_{2}$, where $G_{1}\in\\{C_{3},P_{3},P_{4}\\}$ and
$\Delta(G_{2})\leq 1$. The other implication is straightforward. Thus, (iii)
follows.

Now, we proceed to prove (iv). If $\Delta(G)=\operatorname{n}(G)-1$, then (i)
leads to $\partial_{s}(G)=\operatorname{n}(G)-2$. Moreover, if
$\gamma_{{}_{2}}(G)=2$, then by Theorem 4.4 and (i) we deduce that
$\partial_{s}(G)=\operatorname{n}(G)-2$. Conversely, assume
$\partial_{s}(G)=\operatorname{n}(G)-2$. In this case, Remark 3.2 leads to
$|D_{s}|+2|D_{w}|=2$, which implies that either $|D_{w}|=1$ and $|D_{s}|=0$ or
$|D_{s}|=2$ and $|D_{w}|=0$. Since $D$ is a dominating set of $G$, we obtain
that $\Delta(G)=\operatorname{n}(G)-1$ or $\gamma_{{}_{2}}(G)=2$, as desired.
Therefore, (iv) follows.

Finally, we proceed to prove (v). If either $\gamma_{{}_{2}}(G)=3$ and
$\Delta(G)\leq\operatorname{n}(G)-2$ or $\gamma_{{}_{2}}(G)>3$ and
$\Delta(G)=\operatorname{n}(G)-2$, then by Theorem 4.4, and the statements (i)
and (iv) we deduce that $\partial_{s}(G)=\operatorname{n}(G)-3$. Conversely,
assume that $\partial_{s}(G)=\operatorname{n}(G)-3$. From (i) and (iv) we
deduce that $\Delta(G)\leq\operatorname{n}(G)-2$ and $\gamma_{{}_{2}}(G)\geq
3$. In this case, Remark 3.2 leads to $|D_{s}|+2|D_{w}|=3$, which implies that
either $|D_{w}|=|D_{s}|=1$ or $|D_{s}|=3$ and $|D_{w}|=0$. If
$|D_{w}|=|D_{s}|=1$, then $\Delta(G)=\operatorname{n}(G)-2$, while if
$|D_{s}|=3$ and $|D_{w}|=0$, then $\gamma_{{}_{2}}(G)=3$, which completes the
proof. ∎

##  5 Concluding remarks

In this paper, we have introduced the theory of strong differentials in
graphs. This new branch of the domination theory, allows us to develop the
theory of Italian domination without the use of functions. This interesting
connection is due to Theorem 3.4, which is a Gallai-type theorem. For this
reason, this article presents the challenge of obtaining new results on
Italian domination following this novel approach. As an example, the following
table summarizes some of those results obtained here. The first column
describes the result that combined with Theorem 3.4 leads to the result on the
second column.

From | Result
---|---
Theorem 4.4 | $\gamma_{{}_{I}}(G)\geq\gamma(G)+\sigma(G)$
Proposition 4.7 |  $\gamma_{{}_{I}}(G)=\gamma(G)$ $\longleftrightarrow$ $\gamma_{{}_{2}}(G)=\gamma(G)$
Theorem 4.11 |  $\delta(G)\geq 2$ $\longrightarrow$ $\gamma_{{}_{I}}(G)\leq\frac{1}{2}\left(\operatorname{n}(G)+\gamma(G)\right)$
Theorem 4.14 | $\gamma_{{}_{I}}(G)\geq\gamma_{{}_{R}}(G)-\gamma(G)+1$
Proposition 4.20 |  $\gamma_{{}_{I}}(G)=\frac{2\operatorname{n}(G)}{\Delta(G)+2}$ $\longleftrightarrow$ $\gamma_{{}_{2}}(G)=\frac{2\operatorname{n}(G)}{\Delta(G)+2}$
Corollary 4.23 |  $\delta(G)\geq 2$ $\longrightarrow$ $\gamma_{{}_{I}}(G)\leq\alpha(G)$
Theorem 4.24 |  $G$ connected and $\operatorname{n}(G)\geq 3$ $\longrightarrow$ $\gamma_{{}_{I}}(G)\leq\frac{1}{2}\beta(G)$
Theorem 4.25 |  $\delta(G)\geq 1$ $\longrightarrow$ $\gamma_{{}_{I}}(G)\geq\gamma_{{}_{t2}}(G)$
Proposition 4.26 |  $\gamma_{{}_{t2}}(G)=\gamma_{{}_{2}}(G)$ $\longrightarrow$ $\gamma_{{}_{I}}(G)=\gamma_{{}_{2}}(G)$

## References

  * [1] S. Bermudo. On the differential and Roman domination number of a graph with minimum degree two. _Discrete Appl. Math._ (2017) 232, 64–72.
  * [2] S. Bermudo, H. Fernau, J.M. Sigarreta. The differential and the Roman domination number of a graph. _Appl. Anal. Discrete Math._ (2014) 8 (1), 155–171.
  * [3] 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 Disc. Math._ (2014) 46, 281–288.
  * [4] S. Bermudo, L. De la Torre, A.M. Martín-Caraballo, J.M. Sigarreta. The differential of the strong product graphs. _Int. J. Comput. Math._ (2015) 92 (6) 1124–1134.
  * [5] A. Cabrera Martínez, J.A. Rodríguez-Velázquez. On the perfect differential of a graph. _Quaest. Math._ In press. https://doi.org/10.2989/16073606.2020.1858992
  * [6] M. Chellali, T.W. Haynes, S.T. Hedetniemi, A.A. McRae. Roman $\\{2\\}$-domination. _Discrete Appl. Math._ (2016) 204, 22–28.
  * [7] E. J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi. Roman domination in graphs. _Discrete Math._ (2004) 278 (1–3), 11–22.
  * [8] T. Gallai. Über extreme Punkt- und Kantenmengen. _Annales Universitatis Scientarium Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica_ (1959) 2, 133–138.
  * [9] W. Goddard, M. A. Henning. Generalised domination and independence in graphs. _Congr. Numer._ (1997) 123, 161–171.
  * [10] W. Goddard, M.A. Henning, C.A. McPillan. Semitotal domination in graphs. _Util. Math._ (2014) 94, 67–81.
  * [11] T.W. Haynes, S.T. Hedetniemi, P.J. Slater. Domination in Graphs: Volume 2: Advanced Topics. Chapman & Hall/CRC Pure and Applied Mathematics, Taylor & Francis, 1998.
  * [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] T. W. Haynes, M.A. Henning, L. Volkmann. Graphs with large italian domination number. _Bull. Malays. Math. Sci. Soc._ (2020) 43, 4273–4287.
  * [14] M. A. Henning, A.J. Marcon. Semitotal domination in claw-free cubic graphs. _Ann. Comb._ (2016) 20, 799–813.
  * [15] M. A. Henning, A.J. Marcon. Vertices contained in all or in no minimum semitotal dominating set of a tree. _Discuss. Math. Graph Theory_ (2016) 36, 71–93.
  * [16] M. A. Henning, A. Pandey. Algorithmic aspects of semitotal domination in graphs. _Theoret. Comput. Sci._ (2019) 766, 46–57.
  * [17] M. A. Henning, W.F. Klostermeyer, Italian domination in trees. _Discrete Appl. Math._ (2017) 217, 557–564.
  * [18] W. F. Klostermeyer, G. MacGillivray. Roman, Italian, and 2-domination. _J. Comb. Math. Comb. Comput._ (2019) 108, 125–146.
  * [19] J. L. Lewis, T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, P.J. Slater. Differentials in graphs. _Util. Math._ (2006) 69, 43–54.
  * [20] P. R. L. Pushpam, D. Yokesh. Differentials in certain classes of graphs. _Tamkang J. Math._ (2010) 41 (2), 129–138.


###### Abstract

The probabilistic interpretation of Laplace transforms is used to help to
describe the Laplace Transform $L(s)$ of improper random variables. In
particular, busy periods in queueing models are examined. The value of $L(0)$
is explained in certain special cases.

Laplace Transforms of Improper Random Variables

Janhavi PRABHU

Department of Mathematics

Birla Institute of Technology and Science

Pilani, Goa Campus, India

Myron HLYNKA

Department of Mathematics and Statistics

University of Windsor

Windsor, Ontario, Canada N9B 3P4

This article is distributed under the Creative Commons by-nc-nd Attribution
License. Copyright $\copyright$ 20xx Hikari Ltd.

Mathematics Subject Classification (2020): 60K25, 44A10

Keywords: queueing, Laplace Transform, improper random variables, busy periods

##  1 Introduction

A typical Laplace Transform $L(s)$ for a non-negative continuous proper random
variable (X) probability density function ($f(x)$) satisfies

$L_{X}(s)=\int_{0}^{\infty}f(x)e^{-sx}dx.$

Hence $L_{X}(0)=1$ for proper pdf’s, and $lim_{s\rightarrow\infty}L(s)=0$ and
$L(s)$ is a non-increasing function of $s$.

The probabilistic interpretation of Laplace Transforms was first studied by
van Dantzig ([6]). Further explanations appear in Runnenberg ([5]), in
Kleinrock ([2]), and Roy ([4]). This probabilistic interpretation can be
expressed as follows.

######  Theorem 1.1.

Let $X$ be a continuous random variable with non-negative support having pdf
$f(x)$. Let $Y$ be a “catastrophe” random variable independent of $X$, which
has an exponential distribution with rate $s$. Then

$L_{X}(s)=P(X<Y).$

###### Proof.

Since $F_{Y}(y)=1-e^{-ys}=P(Y\leq y)$, we have $e^{-sy}=P(Y>y)$ so

$L_{X}(s)=\int_{0}^{\infty}f(x)e^{-sx}dx=\int_{0}^{\infty}f(x)P(Y>x)dx=P(X<Y)$

∎

An improper non negative continuous random variable with pdf $f(x)$ is such
that $\int_{0}^{\infty}f(x)dx=1-k$ and $P(X=\infty)=k$, for some $k\in(0,1)$.
See Mynbaev ([3]), for example.

In this paper, we are interested in looking at improper random variables and
interpreting the Laplace transform using the probabilistic interpretation.
This will be done by considering busy periods in an M/M/1 queueing system. We
show the effect of the stability conditions on the appearance of the Laplace
transform. Our analysis will also use branching process methods.

##  2 Analysis of Busy Periods of M/M/1 queueing system

Consider a stable $M/M/1$ queueing system with $\lambda<\mu$ where $\lambda$
is the arrival rate and $\mu$ is the service rate. The Laplace Transform of
the busy period is known and we give a probabilistic interpretation below.

######  Theorem 2.1.

For an $M/M/1$ system with busy period length $B$,

$L_{B}(s)=\dfrac{\mu+\lambda+s-\sqrt{(\mu+\lambda+s)^{2}-4\lambda\mu}}{2\lambda}.$

###### Proof.

Let $L_{i}(s)$ be the time to empty a queueing system if the current load
consists of $i$ customers. A busy period begins with a single customer so
$L_{B}(s)=L_{1}(s)$. Let $Y$ be a catastrophe random variable at rate $s$. Now
the next event could be an arrival (with probability
$\dfrac{\lambda}{\lambda+\mu+s}$) or a completion (with probability
$\dfrac{\mu}{\mu+\lambda+s}$) or a catastrophe. If the next event is a service
completion, that would end the busy period. If the next event is an arrival,
then there would be 2 customers and each of those would have to drop a level
in order to complete the busy period. Then

$\displaystyle L_{B}(s)$ $\displaystyle=P(B<Y)=P(\text{next event is service
completion})$ $\displaystyle\qquad+P(\text{next event is
arrival})P(\text{system empties from 2 customers})$
$\displaystyle=\dfrac{\mu}{\mu+\lambda+s}+\dfrac{\lambda}{\mu+\lambda+s}L_{2}(s)$

But $L_{2}(s)=L_{1}(s)^{2}$ since we need to drop from 2 customers to 1
customer and then 1 customer to zero customers and these are distributionally
the same. Thus

$L_{B}(s)=\dfrac{\mu}{\mu+\lambda+s}+\dfrac{\lambda}{\mu+\lambda+s}L_{B}(s)^{2}$

This is a quadratic and solving yields our result (by keeping the root that is
in the interval [0,1]).

∎

######  Example 2.2.

First we look at the graph of $L_{B}(s)$ when the system is stable. Take
$\lambda=3$ and $\mu=4$. Then $L(s)=\dfrac{7+s-\sqrt{7+s)^{2}-48}}{6}$ See
Figure 1.

Figure 1: LT of busy period (stable case)

######  Example 2.3.

Next, we look at an unstable $M/M/1$ queueing system with $\lambda=4$ and
$\mu=3$ (i,.e. the arrival rate is greater than the service rate). We can
still use the LT expression. Here $L(s)=\dfrac{7+s-\sqrt{7+s)^{2}-48}}{8}$ The
graph now takes the following form.

See Figure 2.

Figure 2: LT of busy period (unstable case)

In our example, we see that $L(0)=.75$. What does this mean? Fortunately, our
probabilistic interpretation of $L_{B}(s)$ gives us this information.

######  Theorem 2.4.

If $L(0)=k$, $k<1$ for an improper non-negative random variable representing a
busy period $B$ in a queueing system, then $k$ represents the probability that
the busy period will end before the system count enters a path which never
returns to 0.

###### Proof.

Since $B$ is an improper random variable, it is possible that $B$ will take
the value $\infty$ (i.e. busy period will never end). Also
$k=lim_{s\rightarrow 0^{+}}L(s)=P(B<Y)$ where $Y$ is exponential at rate
$0^{+}$. So $k$ represents the probability that the busy period will end (and
be finite) at least once before the system number increases and never returns
to 0. ∎

######  Theorem 2.5.

For an $M/M/1$ queueing system, with arrival rate $\lambda$ and service rate
$\mu$, satisfying $\lambda>\mu$, the probability that a busy period ends
before the system count never returns to zero is $\dfrac{\mu}{\lambda}$

###### Proof.

For a discussion of branching processes, see Grinstead and Snell ([1]). For
each customer, define the next generation to consist of 2 items with
probability $\beta_{2}=\dfrac{\lambda}{\lambda+\mu}$ (an arrival plus the
original item) and 0 items with probability
$\beta_{0}=\dfrac{\mu}{\lambda+\mu}$. The probability generating function for
the next generation is $\beta(z)=\beta_{0}+\beta_{2}z^{2}$. Extinction would
mean that the system reaches 0 at some time. By the Fundamental Theorem of
Branching Processes, the probability of extinction $\alpha$ is the smallest
positive real root of $\alpha=\beta(\alpha)$. This is a quadratic in $\alpha$
and we get our result. ∎

######  Example 2.6.

For an $M/M/1$ queueing system, with $\lambda=4$ and $\mu=3$, we previously
obtained a Laplace Transform $L(s)=\dfrac{7+s-\sqrt{7+s)^{2}-48}}{8}$ and
computed $L(0)=6/8=.75$. Our theorem above gives the probability of extinction
as $\mu/\lambda=3/4=.75$ so our results match.

##  3 Conclusions

In this paper, we have explained the value of $L(0)$ for the Laplace Transform
of an improper continuous random variable with positive support. A good
example of such a random variable is the length of a busy period in a queueing
system with arrival rate exceeding service rate.

If we had a complex queueing network with retrials and reneging and balking
and switching of servers, for example, it may still be possible to find the
Laplace Transform in terms of the parameters. In some cases, it may be that
$L(0)<1$. Fixing all but one of the parameters, we can adjust the single
parameter until $L(0)=1$ holds (if possible). The value of the parameter where
this change occurs must be on the boundary of stability of the system. So our
study of $L(0)$ gives information about the boundary conditions, which is very
important.

One final comment about improper Laplace non negative random variables is that
they will have an infinite expected value since there is a positive
probability that the random variable will take the value $\infty$.

Acknowledgements. We acknowledge funding and support from MITACS Global
Internship program.

## References

  * [1] G.M. Grinstead and J.L. Snell, Introduction to Probability: Second Edition, AMS Press, 1997.
  * [2] L. Kleinrock, Queueing Systems Volume 1, John Wiley and Sons, 1975.
  * [3] K.T. Mynbaev, Distributions Escaping to Infinity and the Limiting Power of the Cliff-Ord Test for Autocorrelation, International Scholarly Research Notices, vol. 2012, Article ID 926164, 39 pages, (2012)
https://doi.org/10.5402/2012/926164

  * [4] K.A. Roy, Laplace transforms, probabilities and queues. MSc thesis, Department of Math & Stat, University of Windsor, 1997.
  * [5] J.T. Runnenberg, On the use of collective marks in queueing theory. W. L. Smith and W. E. Wilkinson. editors. Congestion Theory. pages 399-438 University of North Carolina Press. Chape1 Hill. 1965.
  * [6] D. van Dantzig, Sur la methode des functiones generatrices. Colloques internationaux du CNRS, 13: 29-45, (1949)

Received: Month xx, 20xx