Roman domination on 2-connected graphs

Chun Hung Liu, Gerard J. Chang

Research output: Contribution to journalArticlepeer-review

27 Scopus citations


A Roman dominating function of a graph G is a function f: V (G) → {0, 1, 2} such that whenever f(v) = 0, there exists a vertex u adjacent to v such that f(u) = 2. The weight of fis w(f) = ΣvεV (G) f(v). The Roman domination number γR(G) of G is the minimum weight of a Roman dominating function of G. Chambers, Kinnersley, Prince, andWest [SIAM J. Discrete Math., 23 (2009), pp. 1575-1586] conjectured that γR(G) ≤ [2n/3] for any 2-connected graph G of n vertices. This paper gives counterexamples to the conjecture and proves that γR(G) = max{[2n/3], 23n/34} for any 2-connected graph G of n vertices. We also characterize 2-connected graphs G for which γR(G) = 23n/34 when 23n/34 > [2n/3].

Original languageAmerican English
Pages (from-to)193-205
Number of pages13
JournalSIAM Journal on Discrete Mathematics
Issue number1
StatePublished - 2012

ASJC Scopus subject areas

  • General Mathematics


  • 2-connected graph
  • Domination
  • Roman domination

Cite this