Nordhaus-Gaddum bounds for total Roman domination

DOI10.1007/S10878-017-0158-5MaRDI QIDQ1698063zbMATH OpenOpenAlexFDO

Authors J. Amjadi, Seyed Mahmood Sheikholeslami, Marzieh Soroudi

Publication date 21 February 2018

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-017-0158-5

zbMATH Keywords

Nordhaus-Gaddum inequalities total Roman dominating function total Roman domination number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

In this paper, the authors discuss Nordhaus-Gaddum bounds for the total Roman domination number. In the introductory part, the authors recollect graph preliminaries, open neighborhood, closed neighborhood, degree, complement of a graph, diameter and corona graph. Also, they give Roman dominating function, total Roman dominating function and total Roman domination number. They study Nordhaus-Gaddum type result. The authors give the following two results which they use for discussing the results of this paper. 1. If \(G\) is a connected graph of order \(n \geq 3\), then \(\gamma_{\mathrm{tR}}(G)=3\) if and only if \(\Delta(G)=n-1\). 2. If \(G\) is a graph with \(\operatorname{diam}(G) \geq 3\), then \(\gamma_{\mathrm{tR}}(G) \leq 4\). In Section 2, the authors establish some Nordhaus-Gaddum type results for the total Roman domination number. They observe that \(\delta(G) = \min\{\delta(G), \delta(\overline{G})\}\). The authors aim at proving that \(\gamma_{\mathrm{tR}}(G) + \gamma_{\mathrm{tR}}(\overline{G}) \leq n+5\) and \(\gamma_{\mathrm{tR}}(G) \gamma_{\mathrm{tR}}(\overline{G}) \leq 6n-5\),if \(G\) and \(\overline{G}\) are graphs of order \(n\), without isolated vertices. First, they consider the graphs \(G\) and \(\overline{G}\) each of which of diameter two. They determine that the upper bound for total Roman domination number for both \(G\) and \(\overline{G}\) is \(2\delta^\ast(G)+1\). Using the results 1 and 2, they prove the following theorem: ``If \(G\) and \(\overline{G}\) are connected, then \((\gamma_{\mathrm{tR}}(G)-4) (\gamma_{\mathrm{tR}}\overline{G}-4) \leq 4\delta^*(G)-4\). They also prove that the product of total Roman domination number of \(G\) and \(\overline{G}\) is at most \(6n-6\) if \(G\) and \(\overline{G}\) are of order \(n\) with \(\min\{\gamma_{\mathrm{tR}}(G),\gamma_{\mathrm{tR}}(\overline{G})\}=6,7\). They also prove that if \(G\) and \(\overline{G}\) are of order \(n\) with \(\gamma_{\mathrm{tR}}(G),\gamma_{\mathrm{tR}}(\overline{G}) \geq 8\) then \(\gamma_{\mathrm{tR}}(G)+\gamma_{\mathrm{tR}}(\overline{G}) \leq 2\delta^\ast(G)+5 \). Using all the above results, the authors prove that the upper bound of the sum of total Roman domination number of \(G\) and \(\overline{G}\) is \(n+5\), when \(G\) and \(\overline{G}\) have no isolated vertices. Also, they prove that if \(G\) and \(\overline{G}\) are graphs of order \(n\) without isolated vertices, then \(\gamma_{\mathrm{tR}}(G)\gamma_{\mathrm{tR}}(\overline{G}) \leq 6n-5\) with equality if and only if \(G\) is \(5\)-cycle. The authors take the readers from simple concepts to complex concepts in a logical way. The detailed reference is appreciated. The standard of the paper is good. Researchers can make an attempt to find the total Roman domination number of other graph families.

Recommendations

Cites work

Cited in

(22)

This page was built for publication: Nordhaus-Gaddum bounds for total Roman domination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1698063)