Roman domination on 2-connected graphs
Journal
SIAM Journal on Discrete Mathematics
Journal Volume
26
Journal Issue
1
Pages
193-205
Date Issued
2012
Author(s)
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]. © 2012 Society for Industrial and Applied Mathematics.
Type
journal article