Lower Bounds on the Roman and Independent Roman Domination Numbers
Document Type
Article
Publication Date
4-1-2016
Description
A Roman dominating function (RDF) on a graph G is a function f : V (G) → (0, 1,2) satisfying the condition that every vertex u with f(u) = 0 is adjacent to at least one vertex v of G for which f(v) = 2. The weight of a Roman dominating function is the sum f(V ) = Σv∈Vf(v), and the minimum weight of a Roman dominating function f is the Roman domination number γR(G). An RDF f is called an independent Roman dominating function (IRDF) if the set of vertices assigned positive values under f is independent. The independent Roman domination number iR(G) is the minimum weight of an IRDF on G. We show that for every nontrivial connected graph G with maximum and i(G) are, respectively, the domination and independent domination numbers of G. Moreover, we characterize the connected graphs attaining each lower bound. We give an additional lower bound for γR(G) and compare our two new bounds on γR(G) with some known lower bounds.
Citation Information
Chellali, Mustapha; Haynes, Teresa W.; and Hedetniemi, Stephen T.. 2016. Lower Bounds on the Roman and Independent Roman Domination Numbers. Applicable Analysis and Discrete Mathematics. Vol.10(1). 65-72. https://doi.org/10.2298/AADM151112023C ISSN: 1452-8630