Roman Domination on 2-Connected Graphs
Chun‐Hung Liu, Gerard J. Chang · SIAM Journal on Discrete Mathematics · 2012
A Roman dominating function of a graph G is a function f$: V(G) \to \{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 f is $w(f) = \sum_{v \in V(G)} f(v)$. The Roman domination number $\gamma_R(G)$ of G is the minimum weight of a Roman dominating function of G. Chambers, Kinnersley, Prince, and West [SIAM J. Discrete Math., 23 (2009), pp. 1575–1586] conjectured that $\gamma_R(G) \le \lceil 2n/3 \rceil$ for any 2-connected graph G of n vertices. This paper gives counterexamples to the conjecture and proves that $\gamma_R(G) \le \max\{\lceil 2n/3 \rceil, 23n/34\}$ for any 2-connected graph G of n vertices. We also characterize 2-connected graphs G for which $\gamma_R(G) = 23n/34$ when $23n/34 > \lceil 2n/3 \rceil$.