A note on Roman domination in graphs
type: Item
instance of: scholarly article
title: A note on Roman domination in graphs
zbMATH Open document ID: 1108.05072
author: Hua-Ming Xing
author: Xin Chen
author: Xuegang Chen
published in: Discrete Mathematics
publication date: 2006-12-14T00:00:00Z
review text: The main result of the paper is the solution of the problem about a characterization of simple graphs for which \(\gamma_{R}(G) = \gamma(G) + k\) [\textit{E. J. Cockayne} et al., Discrete Math. 278, 11--22 (2004; Zbl 1036.05034)]. Let \(G\) be a connected graph of order \(n\) with the domination number \(\gamma(G) \geq 2.\) The authors of the paper under review give necessary and sufficient conditions for the equality \(\gamma_{R}(G) = \gamma(G) + k\). Here \(\gamma_{R}(G)\) is the Roman domination number of \(G\) and \(k\) is an integer such that \( 2 \leq k \leq \gamma(G).\) A Roman dominating function on a graph \(G = (V,E)\) is a function \(f : V \rightarrow \{0, 1, 2\} \) satisfying the condition that every vertex \(u\) for which \(f(u) = 0\) is adjacent to at least one vertex \(v\) for which \(f(v) = 2.\) The idea is that numbers \(1\) and \(2\) represent either one or two Roman legions stationed at a given location (vertex \(v\)). The weight of a Roman dominating function is the sum of the values \(f(v)\) where \(v\) runs over all \(V.\) The minimum weight of a Roman dominating function on a graph \(G\) is called the Roman domination number of \(G.\) The definition of a Roman dominating function is given implicitly in [\textit{J. Arquilla} and \textit{H. Fredricksen}, Military Operations Research 1 , 3--17 (1995)].
reviewed by: Nikolaj M. Glazunov
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 5080079
zbMATH Keywords: domination number
MaRDI profile type: Publication
full work available at URL: j.disc.2006.06.018
OpenAlex ID: W2012379512
cites work: Roman domination in graphs.
cites work: Q4368728
cites work: Defendens Imperium Romanum: A Classical Problem in Military Strategy
DOI: 10.1016/J.DISC.2006.06.018
Recommended article: ROMAN k-DOMINATION IN GRAPHS
Recommended article: Roman domination in graphs.
Recommended article: Q5217717
Recommended article: A note on \(k\)-Roman graphs
Recommended article: Q4645460
Recommended article: Extremal Problems for Roman Domination
Recommended article: Q5133094
Recommended article: A correction to a paper on Roman \(k\)-domination in graphs
Recommended article: Relations between the Roman \(k\)-domination and Roman domination numbers in graphs
Recommended article: A Nordhaus–Gaddum bound for Roman domination
description: scientific article; zbMATH DE number 5080079