Roman domination on 2-connected graphs

Chun Hung Liu, Gerard J. Chang

Research output: Contribution to journalArticle

23 Scopus citations

Abstract

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 languageEnglish (US)
Pages (from-to)193-205
Number of pages13
JournalSIAM Journal on Discrete Mathematics
Volume26
Issue number1
DOIs
StatePublished - Jun 4 2012

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • 2-connected graph
  • Domination
  • Roman domination

Fingerprint Dive into the research topics of 'Roman domination on 2-connected graphs'. Together they form a unique fingerprint.

  • Cite this