Roman Domination and Mycielski’s Structure in Graphs

Abstract

For a graph \(G = (V,E)\), a function \(f : V \rightarrow \{0,1,2\}\) is called a Roman dominating function (RDF) if for any vertex \(v\) with \(f(v) = 0\), there is at least one vertex \(w\) in its neighborhood with \(f(w) = 2\).

The weight of an RDF \(f\) of \(G\) is the value \(f(V) = \sum_{v\in V} f(v)\). The minimum weight of an RDF of \(G\) is its Roman domination number, denoted by \(\gamma_R(G)\). In this paper, we show that \(\gamma_R(G) + 1 \leq \gamma_R(\mu(G)) \leq \gamma_R(G) + 2\), where \(\mu(G)\) is the Mycielekian graph of \(G\), and then characterize the graphs achieving equality in these bounds.