2009/09/21 by Yunjian Wu, Wu, Yunjian · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO
paper · pdf · doi:10.48550/arxiv.0909.3695
4 pages
arxiv created 2009/09/21 · openalex publication_date 2009/09/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let γ(G) denote the domination number of a graph G. A \it Roman domination function of a graph G is a function f: V→\0,1,2\ such that every vertex with 0 has a neighbor with 2. The \it Roman domination number γR(G) is the minimum of f(V(G))=Σv∈ Vf(v) over all such functions. Let G\square H denote the Cartesian product of graphs G and H. We prove that γ(G)γ(H) ≤ γR(G\square H) for all simple graphs G and H, which is an improvement of γ(G)γ(H) ≤ 2γ(G\square H) given by Clark and Suen \citeCS, since γ(G\square H)≤ γR(G\square H)≤ 2γ(G\square H).