NP-hardness of multiple bondage in graphs

DOI10.1016/J.JCO.2015.04.002MaRDI QIDQ491093zbMATH OpenOpenAlexFDO

Authors Nader Jafari Rad

Publication date 24 August 2015

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2015.04.002

zbMATH Keywords

\(p\)-dominationbondagecomplexitydominationnon-isolating \(p\)-bondage

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of multiple bondage in graphs
• scientific article; zbMATH DE number 6813629
• The algorithmic complexity of bondage and reinforcement problems in bipartite graphs
• Non-isolating bondage in graphs
• Some progress on total bondage in graphs
• Bounds on the bondage number of a graph
• NP-hard graph problems and boundary classes of graphs
• On the bondage number of a graph
• 2-bondage in graphs
• The bondage number of some graphs

Cites work

• 2-bondage in graphs
• \(k\)-domination and \(k\)-independence in graphs: A survey
• Bounds for the 2-domination number of toroidal grid graphs
• Bounds on the bondage number of a graph
• Domination alteration sets in graphs
• scientific article; zbMATH DE number 3914370 (Why is no real title available?)
• 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 1124610 (Why is no real title available?)
• New bounds on the \(k\)-domination number and the \(k\)-tuple domination number
• Non-isolating 2-bondage in graphs
• On bondage numbers of graphs: a survey with some comments
• On the complexity of the bondage and reinforcement problems
• Paired bondage in trees
• Some bounds on the p-domination number in trees
• Some progress on total bondage in graphs
• The \(p\)-bondage number of trees
• The bondage number of a graph
• The total bondage number of grid graphs
• Total bondage number of a graph
• Total domination in graphs

Cited in

(5)

• On the complexity of multiple bondage in graphs
• The algorithmic complexity of bondage and reinforcement problems in bipartite graphs
• On the complexity of the bondage and reinforcement problems
• scientific article; zbMATH DE number 6813629 (Why is no real title available?)
• Semitotal bondage numbers of graphs

This page was built for publication: NP-hardness of multiple bondage in graphs

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