On the complexity of the bondage and reinforcement problems
From MaRDI portal
Publication:413470
DOI10.1016/j.jco.2011.11.001zbMath1239.05138arXiv1109.1657MaRDI QIDQ413470
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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Upper bounds on the bondage number of the strong product of a graph and a tree, ON THE ROMAN BONDAGE NUMBER OF A GRAPH, Upper bounds on the bondage number of a graph, On the double bondage number of graphs products, On the complexity of the outer-connected bondage and the outer-connected reinforcement problems, Trees with 2-reinforcement number three, Edge criticality in graph domination, Minimum edge blocker dominating set problem, On the complexity of reinforcement in graphs, Trees with maximum \(p\)-reinforcement number, An improved upper bound for the bondage number of graphs on surfaces, NP-hardness of multiple bondage in graphs, The \(k\)-rainbow reinforcement numbers in graphs, Bondage number of mesh networks, The total bondage number of grid graphs, Bondage numbers of Mycielski graphs, Bondage number of strong product of two paths, On bondage numbers of graphs: a survey with some comments, Some progress on total bondage in graphs, The bondage number of generalized Petersen graphs \(P(n,2)\), On the \(p\)-reinforcement and the complexity, Domination in certain chemical graphs, The total bondage numbers and efficient total dominations of vertex-transitive graphs, On the complexity of multiple bondage in graphs, Bondage number of the strong product of two trees, The algorithmic complexity of bondage and reinforcement problems in bipartite graphs, Domination parameters in coronene torus network, The average lower reinforcement number of a graph, The Disjunctive Bondage Number and the Disjunctive Total Bondage Number of Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
