On the complexity of reinforcement in graphs

DOI10.7151/dmgt.1898zbMath1350.05126OpenAlexW2530676543MaRDI QIDQ339476

Nader Jafari Rad

Publication date: 11 November 2016

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7151/dmgt.1898

zbMATH Keywords

dominationNP-hardnesstotal dominationreinforcementtotal restrained domination\(k\)-rainbow domination\(p\)-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 (4)

On the complexity of the outer-connected bondage and the outer-connected reinforcement problems ⋮ Reinforcement number of a graph with respect to half-domination ⋮ Rainbow Domination in Graphs ⋮ The restrained k-rainbow reinforcement number of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Total restrained reinforcement in graphs
• Bounds on the 2-rainbow domination number of graphs
• On the complexity of the bondage and reinforcement problems
• A note on total reinforcement in graphs
• \(k\)-domination and \(k\)-independence in graphs: A survey
• Rainbow domination in graphs
• 2-rainbow domination in generalized petersen graphs \(P(n,3)\)
• Note on 2-rainbow domination and Roman domination in graphs
• 2-rainbow domination of generalized Petersen graphs \(P(n,2)\)
• The bondage and reinforcement numbers of \(\gamma_ f\) for some graphs
• On the \(p\)-reinforcement and the complexity
• The algorithmic complexity of bondage and reinforcement problems in bipartite graphs
• On the 2-rainbow domination in graphs
• New bounds on the \(k\)-domination number and the \(k\)-tuple domination number
• On domination and reinforcement numbers in trees
• Total reinforcement number of a graph
• Some bounds on the \(p\)-domination number in trees
• On total restrained domination in graphs
• Bounds for the 2-domination number of toroidal grid graphs
• Total Domination in Graphs

This page was built for publication: On the complexity of reinforcement in graphs