On the signed Roman \(k\)-domination: complexity and thin torus graphs

DOI10.1016/J.DAM.2017.07.026zbMath1372.05164OpenAlexW2752270036MaRDI QIDQ2410261

Zepeng Li, Sandi Klavžar, Jin Xu, Zehui Shao, Pu Wu

Publication date: 17 October 2017

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

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

zbMATH Keywords

computational complexityRoman dominationdischargingtorus graphssigned Roman 2-domination

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

The double Roman domination numbers of generalized Petersen graphs \(P(n, 2)\) ⋮ Double Roman domination in trees ⋮ Trees with equal Roman {2}-domination number and independent Roman {2}-domination number ⋮ Bounds for signed double Roman k-domination in trees ⋮ Unnamed Item

Cites Work

• Strong equality of Roman and weak Roman domination in trees
• Signed Roman \(k\)-domination in digraphs
• Roman domination on strongly chordal graphs
• Signed Roman domination in digraphs
• Signed total Roman domination in digraphs
• Signed Roman edge \(k\)-domination in graphs
• Efficient algorithms for Roman domination on some classes of graphs
• Roman domination in graphs.
• Colorings of plane graphs: a survey
• Signed Roman \(k\)-domination in trees
• Signed Roman domination in graphs
• The differential and the roman domination number of a graph
• Lower bounds on the Roman and independent Roman domination numbers
• Signed Roman \(k\)-domination in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the signed Roman \(k\)-domination: complexity and thin torus graphs