Global triple Roman dominating function

DOI10.1016/J.DAM.2022.02.015MaRDI QIDQ2127628zbMATH OpenOpenAlexFDO

Authors F. Nahani Pour, Mustapha Chellali, H. Abdollahzadeh Ahangar, Seyed Mahmood Sheikholeslami

Publication date 20 April 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2022.02.015

zbMATH Keywords

global triple Roman domination triple Roman domination

Mathematics Subject Classification ID

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

Review text

A triple Roman dominating function (TRD-function) of a graph \(G\) is a function \(f: V(G) \rightarrow \{0, 1, 2, 3, 4\}\) such that if \(f(v) < 3\), then \(f(AN[v]) \ge |AN(v)| + 3\), where \(AN(v)\) is the set of neighbors of \(v\) assigned a non-zero value under \(f\). The minimum weight of a TRD-function on \(G\) is the triple Roman domination number of \(G\), denoted by \(\gamma_{[3R]}(G)\). A global triple Roman dominating function is a TRD-function for both \(G\) and its complement; the global triple Roman domination number is denoted by \(\gamma_{g[3R]}(G)\). It is proved that the global triple Roman dominating problem is NP-complete for bipartite and chordal graphs. Numerous bounds on \(\gamma_{[3R]}(G)\) and \(\gamma_{g[3R]}(G)\) are given and relations between them studied. For instance, if the diameter of \(G\) is at least \(6\) or its radius is \(4\) or \(5\), then \(\gamma_{[3R]}(G) = \gamma_{g[3R]}(G)\), while if \(G\) is triangle-free, then \(\gamma_{g[3R]}(G) \le \gamma_{[3R]}(G) + 4\).

Recommendations

Cited in

(7)

This page was built for publication: Global triple Roman dominating function

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