Roman Domination on 2-Connected Graphs
Academic Article

Overview

Identity

Additional Document Info

View All

Overview

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) = 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.