![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
Let be a positive integer. A nonnegative signed
-subdominating function is a function
satisfying
for at least
vertices
of
. The value
, taking over all nonnegative signed
-subdominating functions
of
, is called the nonnegative signed
-subdomination number of
and denoted by
. If
, then
is the nonnegative signed domination number, introduced in Huang et al. (2013) . In this paper, we obtain several sharp lower bounds of
, which extend some known lower bounds on
.
We also initiate a study of the nonnegative signed -subdomination number in graphs and establish some sharp lower bounds for
in terms of the order and the degree sequence of a graph
.
1 Introduction
Let be a simple graph of order
with vertex set
and size
with edge set
. We use Citation[1] for terminology and notation, which are not defined here. If
, then
is the subgraph of
induced by
. For disjoint subsets
and
of vertices we let
denote the set of edges between
and
.
The open neighborhood of a vertex
is the set of all vertices adjacent to
. Its closed neighborhood is
. In addition, the open and closed neighborhoods of a subset
are
and
, respectively. The degree of a vertex
is
. The minimum and maximum degrees in graph
are denoted by
and
, respectively. A vertex
is called an odd (even) vertex if
is odd (even). For a graph
, let
(
) be the set of odd (even) vertices with
and
.
For a real-valued function the weight of
is
and for a subset
of
we define
, so
. For a positive integer
, a signed
-subdominating function (SkSDF) of G is a function
such that
for at least
vertices
of
. The signed
-subdomination number for a graph
is defined as
. The signed
-subdomination number was introduced and studied by Cockayne and Mynhardt Citation[2]. In the special case where
,
is the signed domination number
. This concept has been extensively explored in the literature; see e.g. Citation[3–5].
A nonnegative signed dominating function (NNSDF) of is defined in Citation[6] as a function
such that
for all vertices
of
. The nonnegative signed domination number (NNSDN) of
is
.
We now introduce a nonnegative signed-subdominating function (NNSkSDF) of
for a positive integer
as a function
such that
for at least
vertices
of
. We define the nonnegative signed
-subdomination number (NNSkSDN) of
by
. A nonnegative signed
-subdominating function of weight
is called a
-function. Note that
. Since every signed
-subdominating function of
is a nonnegative signed
-subdominating function, we deduce that
For a function
of
we define
,
, and
.
In this paper, we establish some new lower bounds on for a general graph in terms of different graph parameters. Some of these bounds improve several lower bounds on
presented in Citation[6,7]. We also initiate a study of nonnegative signed
-subdomination numbers in graphs, and present some sharp lower bounds for
in terms of the order and the degree sequence of
.
Observation 1
Let be an NNSDF of
. For
if
is an even vertex, then
while
if
is an odd vertex.
In this paper, we make use of the following results.
Theorem A
Citation[7] Let be a graph of order
and size
. Then
Theorem B
Citation[7] Let be a graph of order
, size
and minimum degree
. Then
Theorem C
Citation[4] For ,
Corollary 2
Citation[8] For any -regular graph
of order
,
, for
even. Furthermore this bound is sharp.
Proposition 3
Citation[6] Let be a complete graph. Then
when
is even and
when
is odd.
Theorem D
Citation[6] For any graph with maximum degree
and minimum degree
, we have
2 Lower bounds on the NNSDNs of graphs
In this section, we present some new sharp lower bounds for in terms of
where
is the number of even vertices in a graph
. We begin with the following lemma.
Lemma 4
Let be an NNSDF of a simple connected graph
. Then,
1. |
| ||||
2. |
|
Proof
For , let
and
denote the numbers of vertices of
and
, respectively, which are adjacent to
. Clearly,
. Since
, for every
,
, and for every
,
. Hence, if
, then
and if
, then
.
1. | Counting the number of edges in | ||||
2. | Consider the subgraph |
In the next theorem we present some lower bounds on . By using Lemma 4 and graph parameters such as order, size, number of even vertices, maximum and minimum degrees we obtain some new lower bounds for
.
Theorem 5
Let be a simple connected graph of order
, minimum degree
, maximum degree
and the number of even vertices
. Then
1. |
| ||||
2. |
| ||||
3. |
| ||||
4. |
| ||||
5. |
|
Proof
Let be a
-function. Let
and
.
1. | Since | ||||
2. | Since | ||||
3. | Using Lemma 4(1), the facts | ||||
4. | Consider | ||||
5. | By Parts (4) and (2) we have
|
From Theorem 5(1) (3), we have the following result.
Corollary 6
For , if
is an
-regular graph of order
, then
Furthermore, these bounds are sharp.
For by Observation 1 when
is even, we have the same bound presented in Corollary 2 by Henning. In order to show that the bounds presented in Theorem 5 are sharp, we will give a graph
and construct a
-function
such that
achieves the lower bounds. Our bounds for some of these graphs are attainable while the corresponding bounds given in Theorems A, B, and D are not. In fact, trivial examples such as
are sufficient for this. By Proposition 3 it is easy to see that
attains all the five bounds in Theorem 5 while the bound in Theorem A shows that
and the bound in Theorem B is not more than
. Moreover, by Theorem C,
attains the lower bounds in Theorem 5(1)
(3), when
while the bounds in Theorems A, B and D are not more than
. Besides, we can construct a non-complete graph with an arbitrary large order which attains the lower bounds in Theorem 5(1)
(3) as follows. Letting
be a positive integer, we consider a cycle of length
. For every edge, we include an additional vertex being adjacent to both endpoints of the corresponding edge. The obtained graph is denoted by
. It is easy to check that
is a graph with
,
,
,
and
. Define a function
as follows:
for
and
for
. It is easy to verify that
is a
-function with
and bounds in Theorem 5(1)
(3) are also
, which implies that
is sharp for these bounds. However,
does not attain the corresponding bounds given in Theorems A, B and D, which are
,
, and
, respectively. Next, we show that there is also a graph
different from
such that
reaches lower bounds in Theorem 5(4)
(5). Let
be the Hajós graph. We can verify that
, and
is sharp for presented bounds in Theorem 5(4)
(5).
3 Lower bounds on the NNSkSDNs of graphs
In this section, we initiate a study of the nonnegative signed -subdomination number in graphs. we present some lower bounds on the nonnegative signed
-subdomination number of a graph in terms of the order and the degree sequence. We begin with the following lemma.
Lemma 7
Let be a graph and
be a positive integer. Let
be a
-function. Let
,
,
and
. Then,
Proof
Note that if , then
. For
,
. So, if
, then
and
. Similarly, if
, then
and
.
Counting the number of edges in in two ways, we conclude that
By adding
to the both sides of the inequality we have
and this completes the proof.□
Theorem 8
For any graph with degree sequence
and any positive integer
,
1. |
| ||||
2. |
|
Furthermore, these bounds are sharp.
Proof
Let be a
-function. Let
and
.
1. | Since | ||||
2. | Obviously, |
Now suppose that , considering that
, we can immediately obtain those two bounds in Theorem 5(2) and (3) from the lower bounds of Theorem 8, respectively. Since lower bounds presented in Theorem 5 are sharp, so there exist graphs whose
receive lower bounds in Theorem 8. Therefore, these bounds are sharp.□
From Theorem 8(1) or (2) the following result can be immediately deduced.
Corollary 9
For , if
is an
-regular graph of order
, then
Furthermore, these bounds are sharp.
References
- WestD.B., Introduction to Graph Theory2000Prentice-Hall, Inc
- CockayneE.J.MynhardtC.M., On a generalization of signed dominating function of graphs Ars Combin.1996 235–245
- ChenW.SongE., Lower bounds on several versions of signed domination number Disceret Math. 3082008 1837–1846
- DunbarJ.HedetniemiS.T.HenningM.A.SlaterP.J., Signed Domination in Graphs, Graph Theory, Combinatorics, and Applications, Vol. 11995WileyNew York311–322
- HaynesT.W.HedetniemiS.T.SlaterP.J., Domination in Graphs: Advance Topics1998Marcel Dekker, Inc.New York
- HuangZ.LiW.FengZ.XingH., On nonnegative signed domination in graphs and its algorithmic complexity J. Netw. (2)2013 365–372
- AtapourM.SheikholeslamiS.M., On the nonnegative signed domination numbers in graphs Electron. J. Graph Theory Appl. (2)2016 231–237
- HenningM.A., Domination in regular graphs Ars Combin.1996 263–271