Open Journal of Discrete Mathematics
Vol.3 No.1(2013), Article ID:27391,3 pages DOI:10.4236/ojdm.2013.31011

Reverse Total Signed Vertex Domination in Graphs

Wensheng Li

Department of Mathematics and Information Sciences, Langfang Teachers College, Langfang, China

Email: wsli@live.cn

Received November 20, 2012; revised December 20, 2012; accepted December 27, 2012

Keywords: Reverse Total Signed Vertex Domination; Upper Bounds; Complete Bipartite Graph

ABSTRACT

Let be a simple graph with vertex set V and edge set E. A function is said to be a reverse total signed vertex dominating function if for every, the sum of function values over and the elements incident to is less than zero. In this paper, we present some upper bounds of reverse total signed vertex domination number of a graph and the exact values of reverse total signed vertex domination number of circles, paths and stars are given.

1. Introduction

In this paper we shall use the terminology of [1]. Let be a simple graph with vertex set and edge set. Let,. For every, the open neighborhood of, denoted by, is a set and the closed neighborhood of, denoted by, is a set. We write for the degree of a vertex and the maximum and minimum degree of are denoted by and, respectively. For every, the edge-closed neighborhood of, denoted by, is

.

Many domination parameters in graphs has been studied richly [2-4] A function is a signed dominating function if for every vertex

,.

The weight of is the sum of the function values of all vertices in. The signed domination number of is the minimum weight of signed dominating functions on. This concept was introduced by Dunbar et al. [5] and has been studied by several authors [6-9]. As an extension of the signed domination, we give the definition of the reverse total signed vertex domination in a graph.

Definition 1. Let be a simple graph. A reverse total signed vertex dominating function of is a function such that

for all. The reverse total signed vertex domination number of, denoted by, is the maximum weight of a reverse total signed vertex dominating function of. A reverse total signed vertex dominating function is called a -function of if .

2. Properties of Reverse Total Signed Vertex Domination

Proposition 1 For any graph,

.

Proof. Let be a -function of. Then

.

Let

,

,

,

.

Then

.

Therefore.

Propositon 2 For any graph,.

Proof. Let be a -function of. Then for every, and we have

Thus.

Propositon 3 For any graph,.

Proof. Let be a -function of., , and are defined as Proposition 2. Then

.

We define two induced graphs and of as follows:

, ,.

Then for every,

and. For every, we have

and. Thus

Therefore

Since

we have. Therefore.

Propositon 4 For any star,.

Proof. Let be a -function. Let

,

,

where is the center of. Since for every, , we have

.

On the other hand, consider the function

such that

,.

Then is a reverse total signed vertex dominating function on and

.

Thus, which implies that .

Propositon 5 For any circle,.

Proof. Let be a -function of. Let

,.

Since for every, , we have

.

Thus

.

Therefore.

On the other hand, consider the mapping

such that

,.

Then is a reverse total signed vertex dominating function on and. Therefore

which implies.

Propositon 6 For any complete bipartite graph,.

Proof. Letbe a -function. Let

, ,

and

.

Since for every, , we have . Therefore

.

On the other hand, consider the mapping

such that, for,

for and. Then is a reverse total signed vertex dominating function on

and. Thereforewhich implies.

3. Acknowledgements

This work was supported by the Natural Science Foundation of Hebei Province (A2012408002), the Educational Commission of Hebei Province (ZH2011122, Z2011157) and Langfang Teachers College (LSZQ201106).

REFERENCES

  1. J. A. Bondy and V. S. R. Murty, “Graph Theory with Application,” Elsevier, Amsterdam, 1976.
  2. T. T. Chelvam and G. Kalaimurugan, “Bounds for Domination Parameters in Cayley Graphs on Dihedral Group,” Open Journal of Discrete Mathematics, Vol. 2, No. 1, 2012, pp. 5-10. doi:10.4236/ojdm.2012.21002
  3. T. W. Haynes, S. T. Hedetniemi and P. J. Slater, “Fundamentals of Domination in Graphs,” Marcel Dekker, New York, 1998.
  4. G. T. Wang and G. Z. Liu, “Rainbow Matchings in Properly Colored Bipartite Graphs,” Open Journal of Discrete Mathematics, Vol. 2, No. 2, 2012, pp. 62-64. doi:10.4236/ojdm.2012.22011
  5. J. E. Dunbar, S. T. Hedetniemi, M. A. Henning and P. J. Slater, “Signed Domination in Graphs,” Combinatorics, Graph Theory, Applications, Vol. 1, 1995, pp. 311-322.
  6. O. Favaron, “Signed Domination in Regular Graphs,” Discrete Mathematics, Vol. 158, No. 1, 1996, pp. 287- 293. doi:10.1016/0012-365X(96)00026-X
  7. Z. Zhang, B. Xu, Y. Li and L. Liu, “A Note on the Lower Bounds of Signed Domination Number of a Graph,” Discrete Mathematics, Vol. 195, No. 1, 1999, pp. 295-298. doi:10.1016/S0012-365X(98)00189-7
  8. X. Z. Lv, “Total Signed Domination Numbers of Graphs,” Science in China A: Mathematics, Vol. 37, 2007, pp. 573- 578.
  9. X. Z. Lv, “A Lower Bound on the Total Signed Domination Numbers of Graphs,” Science in China Series A: Mathematics, Vol. 50, 2007, pp. 1157-1162.