Roman and total domination

Abstract

A set S of vertices is a total dominating set of a graph G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set is the total domination number γ_t(G). A Roman dominating function on a graph G is a function ƒ : V (G) → {0, 1, 2} satisfying the condition that every vertex u with ƒ(u) = 0 is adjacent to at least one vertex v of G for which ƒ(v) = 2. The minimum of ƒ(V (G)) = Σ _{u∈V (G)} ƒ(u) over all such functions is called the Roman domination number γ_R(G). We show that γ_t(G) ≤ γ_R(G) with equality if and only if γ_t(G) = 2_γ (G), where γ(G) is the domination number of G. Moreover, we characterize the extremal graphs for some graph families.

Keywords: Roman domination, total domination.