Lower Bounds on the Roman and Independent Roman Domination Numbers

Applicable Analysis and Discrete Mathematics

article

Mustapha Chellali¹  Teresa W. Haynes²  Stephen T. Hedetniemi⁴ 

[1] LAMDA-RO Laboratory, Department of Mathematics, University of Blida;Department of Mathematics, East Tennessee State University;Department of Mathematics, University of Johannesburg Auckland Park South Africa;School of Computing, Clemson University Clemson

关键词: Roman domination;    independent domination;    total domination;    ve-domination;   

DOI  :  10.2298/AADM151112023C

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Beogradu * Elektrotehnicki Fakultet / University of Belgrade, Faculty of Electrical Engineering

【 摘 要 】

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 adjacentto at least one vertex v of G for which f(v) = 2. The weight of a Romandominating function is the sum f(V ) = Pv∈Vf(v), and the minimum weight ofa Roman dominating function f is the Roman domination number γR(G). AnRDF f is called an independent Roman dominating function (IRDF) if the setof vertices assigned positive values under f is independent. The independentRoman domination number iR(G) is the minimum weight of an IRDF on G.We show that for every nontrivial connected graph G with maximum degree∆, γR(G) ≥∆ + 1∆γ(G) and iR(G) ≥ i(G) + γ(G)/∆, where γ(G) 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 newbounds on γR(G) with some known lower bounds.

【 授权许可】

Unknown