On the complexity of the bondage and reinforcement problems

DOI10.1016/j.jco.2011.11.001zbMath1239.05138arXiv1109.1657OpenAlexW1970112701MaRDI QIDQ413470

Fu-Tao Hu, Jun-Ming Xu

Publication date: 7 May 2012

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

Full work available at URL: https://arxiv.org/abs/1109.1657

zbMATH Keywords

complexitydominationreinforcementbondage

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 (max. 100)

Edge criticality in graph domination ⋮ Minimum edge blocker dominating set problem ⋮ The Disjunctive Bondage Number and the Disjunctive Total Bondage Number of Graphs ⋮ On the complexity of reinforcement in graphs ⋮ Bondage number of the strong product of two trees ⋮ The bondage number of generalized Petersen graphs \(P(n,2)\) ⋮ Trees with maximum \(p\)-reinforcement number ⋮ The average lower reinforcement number of a graph ⋮ Bondage number of strong product of two paths ⋮ On bondage numbers of graphs: a survey with some comments ⋮ An improved upper bound for the bondage number of graphs on surfaces ⋮ The algorithmic complexity of bondage and reinforcement problems in bipartite graphs ⋮ NP-hardness of multiple bondage in graphs ⋮ Upper bounds on the bondage number of the strong product of a graph and a tree ⋮ The \(k\)-rainbow reinforcement numbers in graphs ⋮ On the \(p\)-reinforcement and the complexity ⋮ Bondage number of mesh networks ⋮ ON THE ROMAN BONDAGE NUMBER OF A GRAPH ⋮ Domination in certain chemical graphs ⋮ Some progress on total bondage in graphs ⋮ The total bondage number of grid graphs ⋮ On the complexity of the outer-connected bondage and the outer-connected reinforcement problems ⋮ Bondage numbers of Mycielski graphs ⋮ On the double bondage number of graphs products ⋮ Domination parameters in coronene torus network ⋮ The total bondage numbers and efficient total dominations of vertex-transitive graphs ⋮ On the complexity of multiple bondage in graphs ⋮ Upper bounds on the bondage number of a graph ⋮ The restrained k-rainbow reinforcement number of graphs ⋮ Trees with 2-reinforcement number three

Cites Work

• A note on total reinforcement in graphs
• Restrained bondage in graphs
• A survey of selected recent results on total domination in graphs
• Reinforcement numbers of digraphs
• The bondage number of a graph
• Restrained domination in graphs
• The total domination and total bondage numbers of extended de Bruijn and Kautz digraphs
• Total reinforcement number of a graph
• Total bondage number of a graph
• On the Algorithmic Complexity of Total Domination
• Total domination in graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Theory and Application of Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of the bondage and reinforcement problems