On the complexity of multiple bondage in graphs

DOI10.1016/J.TCS.2019.09.008MaRDI QIDQ2333796zbMATH OpenOpenAlexFDO

Authors Nader Jafari Rad

Publication date 13 November 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.09.008

zbMATH Keywords

complexity3-SATbondage\(p\)-bondage\(p\)-total bondage\(p\)-tuple bondagedouble bondage

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)

Recommendations

• NP-hardness of multiple bondage in graphs
• scientific article; zbMATH DE number 6813629
• On the complexity of the bondage and reinforcement problems
• The algorithmic complexity of bondage and reinforcement problems in bipartite graphs
• Complexity and bounds for disjunctive total bondage

Cites work

• scientific article; zbMATH DE number 5851743 (Why is no real title available?)
• 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?)
• scientific article; zbMATH DE number 1792607 (Why is no real title available?)
• 2-bondage in graphs
• Bounds for the 2-domination number of toroidal grid graphs
• Bounds on the bondage number of a graph
• Domination alteration sets in graphs
• Double bondage in graphs
• NP-hardness of multiple bondage in graphs
• New results about the bondage number of a graph
• Non-isolating 2-bondage in graphs
• On bondage numbers of graphs: a survey with some comments
• On the bondage number of a graph
• On the complexity of the bondage and reinforcement problems
• Some bounds on the \(p\)-domination number in trees
• The \(p\)-bondage number of trees
• The \(p\)-domination number of complete multipartite graphs
• The algorithmic complexity of bondage and reinforcement problems in bipartite graphs
• The bondage number of a graph
• Total domination in graphs
• \(k\)-domination and \(k\)-independence in graphs: A survey

Cited in

(6)

• The algorithmic complexity of bondage and reinforcement problems in bipartite graphs
• On the complexity of the bondage and reinforcement problems
• Complexity and bounds for disjunctive total bondage
• scientific article; zbMATH DE number 6813629 (Why is no real title available?)
• NP-hardness of multiple bondage in graphs
• Non-isolating bondage in graphs

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

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