Outer-independent total Roman domination in graphs

DOI10.1016/J.DAM.2018.12.018MaRDI QIDQ2328098zbMATH OpenOpenAlexFDO

Authors Dorota Kuziak, Abel Cabrera Martínez, Ismael G. Yero

Publication date 9 October 2019

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

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

zbMATH Keywords

outer-independent total Roman dominationRoman dominationtotal dominationtotal Roman dominationvertex coververtex independence

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

\textit{E. J. Cockayne} et al. [Discrete Math. 278, No. 1--3, 11--22 (2004; Zbl 1036.05034)] have introduced the concept of Roman domination in graphs. The authors start by establishing the relationship between outer independent Roman domination number and outer independent total Roman domination number. A major computational result in this paper namely ``the computation of outer independent total Roman domination is NP-complete even when restricted to planar graphs of maximum degree at most 3 is very interesting. Even though the proof techniques are routine the way in which they are presented definitely deserve appreciation.

Recommendations

• Outer independent Roman dominating functions in graphs
• On the outer independent total double Roman domination in graphs
• Algorithmic Aspects of Outer-Independent Total Roman Domination in Graphs
• Algorithmic aspects of outer independent Roman domination in graphs
• Relating the outer-independent total Roman domination number with some classical parameters of graphs
• On total Roman domination in graphs
• Total roman domination in graphs
• Independent Roman \(\{2 \}\)-domination in graphs
• Further results on the independent Roman domination number of graphs
• Independent double Roman domination in graphs

Cites work

• A characterization of Roman trees
• A note on the independent Roman domination in unicyclic graphs
• A survey of selected recent results on total domination in graphs
• Edge roman domination in graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 6815662 (Why is no real title available?)
• Mixed Roman domination in graphs
• On maximal Roman domination in graphs
• On the strong Roman domination number of graphs
• On trees attaining an upper bound on the total domination number
• Outer independent Roman dominating functions in graphs
• Properties of independent Roman domination in graphs
• Roman \(k\)-domination in graphs
• Roman domination in graphs.
• Roman domination on strongly chordal graphs
• Signed Roman domination in graphs
• The distance Roman domination numbers of graphs
• Total domination in graphs
• Total roman domination in graphs
• Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number

Cited in

(16)

• Independent Roman \(\{2 \}\)-domination in graphs
• Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination
• Relating the outer-independent total Roman domination number with some classical parameters of graphs
• On the outer independent double Roman domination number
• Outer independent Roman dominating functions in graphs
• Varieties of Roman domination. II
• The total co-independent domination number of some graph operations
• Algorithmic aspects of outer independent Roman domination in graphs
• Roman domination stability in graphs
• On the outer independent total double Roman domination in graphs
• scientific article; zbMATH DE number 7693187 (Why is no real title available?)
• Algorithmic Aspects of Outer-Independent Total Roman Domination in Graphs
• Outer independent double Italian domination: Complexity, characterization
• On the total version of the covering Italian domination problem
• Outer-independent Roman domination on Cartesian product of paths
• On the outer-independent total (Roman) domination number of some graph operators

This page was built for publication: Outer-independent total Roman domination in graphs

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