Roman and Total Domination
Document Type
Article
Publication Date
12-4-2015
Description
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 f : V (G) → {0, 1, 2} satisfying the condition that every vertex u with f (u)=0 is adjacent to at least one vertex v of G for which f (v)=2. The minimum of f (V (G))=∑u ∈ V (G) f (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.
Citation Information
Chellali, Mustapha; Haynes, Teresa W.; and Hedetniemi, Stephen T.. 2015. Roman and Total Domination. Quaestiones Mathematicae. Vol.38(6). 749-757. https://doi.org/10.2989/16073606.2015.1015647 ISSN: 1607-3606