2012/01/01 by Chun-Hung Liu, Chun‐Hung Liu, Gerard J. Chang
Computer Science · Economics, Econometrics and Finance · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Game Theory and Voting Systems
paper · doi:10.1137/080733085
openalex publication_date 2012/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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 f is 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, and West [SIAM J. Discrete Math., 23 (2009), pp. 1575–1586] conjectured that γR(G) ≤ \lceil 2n/3 \rceil for any 2-connected graph G of n vertices. This paper gives counterexamples to the conjecture and proves that γR(G) ≤ 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 γR(G) = 23n/34 when 23n/34 > \lceil 2n/3 \rceil.