Signed Roman domination in graphs

H. Abdollahzadeh Ahangar, Michael A. Henning, Christian Löwenstein, Yancai Zhao, Vladimir Samodivkin

Research output: Contribution to journalArticlepeer-review

80 Citations (Scopus)

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 γsR(G) 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 γ sR(G)≥3{n+1} - n - 3, and we characterize the extremal graphs.

Original languageEnglish
Pages (from-to)241-255
Number of pages15
JournalJournal of Combinatorial Optimization
Volume27
Issue number2
DOIs
Publication statusPublished - Feb 2014

Keywords

  • Roman domination
  • Signed Roman domination
  • Signed domination

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Signed Roman domination in graphs'. Together they form a unique fingerprint.

Cite this