Defending the Roman Empire---a new strategy
type: Item
instance of: scholarly article
title: Defending the Roman Empire---a new strategy
zbMATH Open document ID: 1024.05068
DOI: 10.1016/S0012-365X(02)00811-7
author: Michael A. Henning
author: Stephen T. Hedetniemi
published in: Discrete Mathematics
publication date: 2003-06-09T00:00:00Z
review text: Let \(G= (V,E)\) be a graph and let \(f\) be a function \(f: V\to \{0,1,2\}\). A vertex \(u\) with \(f(u)= 0\) is undefended with respect to \(f\) if it is not adjacent to a vertex of positive weight. A function \(f\) is a weak Roman domination function if each \(u\in V\) with \(f(u)= 0\) is adjacent to a vertex \(v\) with \(f(v)> 0\) such that the function \(f': V\to\{0,1,2\}\) defined by \(f'(u)= 1\), \(f'(v)= f(v)- 1\) and \(f'(w)= f(w)\), \(w\in V- \{u,v\}\) has no undefended vertex. The weight of \(f\) is \(w(f)= \sum_{v\in V} f(v)\). The weak Roman domination number \(\gamma_r(G)\) is the minimum weight of a weak Roman domination function of \(G\). It is proved that \(\gamma(G)\leq \gamma_r(G)\leq 2\gamma(G)\) for every graph \(G\).
reviewed by: G. Gutin
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 1924769
zbMATH Keywords: forests
zbMATH Keywords: weak Roman domination number
MaRDI profile type: Publication
cites work: Dominating Sets in Chordal Graphs
cites work: Roman domination in graphs.
cites work: Q4863436
cites work: Q4368728
cites work: Q4368729
full work available at URL: s0012-365x(02)00811-7
OpenAlex ID: W2087928776
Recommended article: Defending the Roman Empire from multiple attacks
Recommended article: Defendens Imperium Romanum: A Classical Problem in Military Strategy
Recommended article: Some progress on the restrained Roman domination
Recommended article: R<scp>OMAN DOMINATION</scp>: a parameterized perspective†
Recommended article: SOFSEM 2006: Theory and Practice of Computer Science
Recommended article: On Byzantine generals with alternative plans
Recommended article: Q4616111
Recommended article: The strategy of conquest
description: scientific article; zbMATH DE number 1924769