Defending the Roman Empire - A new strategy

Michael A. Henning, Stephen T. Hedetniemi

Research output: Contribution to journalArticlepeer-review

140 Citations (Scopus)

Abstract

Motivated by an article by Ian Stewart (Defend the Roman Empire!, Scientific American, Dec. 1999, pp. 136-138), we explore a new strategy of defending the Roman Empire that has the potential of saving the Emperor Constantine the Great substantial costs of maintaining legions, while still defending the Roman Empire. In graph theoretic terminology, let G=(V,E) be a graph and let f be a function f: V→{0,1,2}. A vertex u with f(u)=0 is said to be undefended with respect to f if it is not adjacent to a vertex with positive weight. The function f is a weak Roman dominating function (WRDF) if each vertex u with f(u)=0 is adjacent to a vertex v with f(v) 0 such that the function f: V→{0,1,2}, defined by f(u)=1, f(v)=f(v)-1 and f(w)=f(w) if w∈V-{u,v}, has no undefended vertex. The weight of f is w(f)=∑ v∈Vf(v). The weak Roman domination number, denoted γ r(G), is the minimum weight of a WRDF in G. We show that for every graph G, γ(G)γ r(G)2γ(G). We characterize graphs G for which γ r(G)=γ(G) and we characterize forests G for which γ r(G)=2γ(G).

Original languageEnglish
Pages (from-to)239-251
Number of pages13
JournalDiscrete Mathematics
Volume266
Issue number1-3
DOIs
Publication statusPublished - 6 May 2003
Externally publishedYes

Keywords

  • Domination number
  • Forests
  • Weak Roman domination number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Defending the Roman Empire - A new strategy'. Together they form a unique fingerprint.

Cite this