Abstract
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 language | English |
---|---|
Pages (from-to) | 98-105 |
Number of pages | 8 |
Journal | Discrete Applied Mathematics |
Volume | 186 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2015 |
Keywords
- Signed Roman k-dominating function
- Signed Roman k-domination number
- Tree
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics