2009/01/01 by Erin Wolf Chambers, Erin W. Chambers, Bill Kinnersley +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Discrete mathematics #Domination analysis #Graph #Mathematics #Vertex (graph theory)
paper · doi:10.1137/070699688
openalex publication_date 2009/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
A Roman dominating function of a graph G is a labeling f\colon V(G)→\0,1,2\ such that every vertex with label 0 has a neighbor with label 2. The Roman domination number γR(G) of G is the minimum of ∑v∈ V(G)f(v) over such functions. Let G be a connected n-vertex graph. We prove that γR(G)≤4n/5, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for γR(G)+γR(G) and γR(G)γR(G), improving known results for domination number. We prove that γR(G)≤8n/11 when δ(G)≥2 and n≥9, and this is sharp.