Roman Domination on 2-Connected Graphs Academic Article uri icon


  • 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) = vV (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]. 2012 Society for Industrial and Applied Mathematics.

published proceedings

  • SIAM Journal on Discrete Mathematics

author list (cited authors)

  • Liu, C., & Chang, G. J.

citation count

  • 23

complete list of authors

  • Liu, Chun-Hung||Chang, Gerard J

publication date

  • January 2012