Signed Roman k-domination in trees

Michael A. Henning, Lutz Volkmann

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


Let k ≥ 1 be an integer, and let G be a finite and simple graph with vertex set V(G). A signed Roman k-dominating function (SRkDF) on a graph G is a functionf: V(G) → {-1, 1, 2} satisfying the conditions that (i) Σx∈N[ν] f (x) ≥ k for each vertex ν ∈ V(D), where N[ν] is the closed neighborhood of ν, and (ii) every vertex u for which f (u) = - 1 is adjacent to at least one vertex v for which f (ν) = 2. The weight of an SRkDFf is Σν∈V(G) f (v). The signed Roman k-domination number γksR (G) of G is the minimum weight of an SRkDF on G. In this paper we establish a tight lower bound on the signed Roman 2-domination number of a tree in terms of its order. We prove that if T is a tree of order n ≥ 4, then γ 2sR(T) ≥ 10n+24/17 and we characterize the infinite family of trees that achieve equality in this bound.

Original languageEnglish
Pages (from-to)98-105
Number of pages8
JournalDiscrete Applied Mathematics
Issue number1
Publication statusPublished - 2015


  • Signed Roman k-dominating function
  • Signed Roman k-domination number
  • Tree

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


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

Cite this