Signed Roman domination in graphs |
| |
Authors: | H. Abdollahzadeh Ahangar Michael A. Henning Christian Löwenstein Yancai Zhao Vladimir Samodivkin |
| |
Affiliation: | 1. Babol University of Technology, Babol, Iran 2. University of Johannesburg, Johannesburg, South Africa 3. Wuxi City College of Vocational Technology, Jiangsu, China 4. University of Architecture Civil Engineering and Geodesy, Sofia, Bulgaria
|
| |
Abstract: | In this paper we continue the study of Roman dominating functions in graphs. A signed Roman dominating function (SRDF) on a graph G=(V,E) is a function f:V→{?1,1,2} satisfying the conditions that (i) the sum of its function values over any closed neighborhood is at least one and (ii) for every vertex u for which f(u)=?1 is adjacent to at least one vertex v for which f(v)=2. The weight of a SRDF is the sum of its function values over all vertices. The signed Roman domination number of G is the minimum weight of a SRDF in G. We present various lower and upper bounds on the signed Roman domination number of a graph. Let G be a graph of order n and size m with no isolated vertex. We show that $gamma _{mathrm{sR}}(G) gefrac{3}{sqrt{2}} sqrt{n} - n$ and that γ sR(G)≥(3n?4m)/2. In both cases, we characterize the graphs achieving equality in these bounds. If G is a bipartite graph of order n, then we show that $gamma_{mathrm{sR}}(G) ge3sqrt{n+1} - n - 3$ , and we characterize the extremal graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|