Some progress on the restrained Roman domination (Q2021658)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some progress on the restrained Roman domination |
scientific article |
Statements
Some progress on the restrained Roman domination (English)
0 references
27 April 2021
0 references
Let \(G = (V, E)\) be a graph. A Roman dominating function \(f = (V_0, V_1, V_2)\) is called restrained Roman dominating function (for short, RRDF) if the induced subgraph \(G[V_0]\) has no isolated vertex. The restrained Roman domination number of \(G\), denoted by \(\gamma_{rR}(G)\), is the minimum weight of an RRDF on \(G\). A \(\gamma_{rR}(G)\)-function \(f\) is an RRDF of \(G\) with \(w( f ) = \gamma_{rR}(G)\). In this paper, the authors study the graph \(G\) with \(\gamma_{rR}(G)=3\) and \(\gamma_{rR}(G)=n-1\) where \(n\) is the order of \(G\). One of the main results is: Theorem. Let \(\overline{G}\) be the complement of \(G\). For any connected graph \(G\) of order \(n \ge 5\), \[6\le \gamma_{rR}(G)+ \gamma_{rR}(\overline{G})\le n+5.\] The upper bound holds with equality if and only if \(G = C_5\) and the lower bound holds with equality if and only if \(G\) satisfies one of the following conditions: \begin{itemize} \item[(i)] \(\Delta(G) = n-1\), \(G\) has exactly one leaf and \(G\) has no vertex of degree \(n-2\). \item[(ii)] \(\Delta(G) = n-1\), \(\delta(G) = 2\) and \(G\) has a vertex \(u\) of degree \(2\) such that the induced subgraph \(G[V(G)-N[u]]\) has no universal vertex. \end{itemize}
0 references
Roman domination number
0 references
restrained Roman domination number
0 references
Nordhaus-Gaddum inequalities
0 references