The algorithmic complexity of minus domination in graphs

DOI10.1016/0166-218X(95)00056-WzbMath0848.05041OpenAlexW2043805568MaRDI QIDQ1917346

Stephen T. Hedetniemi, Jean E. Dunbar, Michael A. Henning, Alice A. McRae, Wayne Goddard

Publication date: 6 October 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(95)00056-w

zbMATH Keywords

treealgorithmminus domination numberNP-completeweightminus dominating function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items (24)

The algorithmic complexity of the minus clique-transversal problem ⋮ Upper minus domination in a claw-free cubic graph ⋮ Algorithmic Aspect of Minus Domination on Small-Degree Graphs ⋮ Minus domination in regular graphs ⋮ The minus total k-domination numbers in graphs ⋮ Efficient minus and signed domination in graphs ⋮ Lower bounds on the minus domination and \(k\)-subdomination numbers. ⋮ Minus domination number in \(k\)-partite graphs. ⋮ Upper minus total domination in small-degree regular graphs ⋮ Variations of \(Y\)-dominating functions on graphs ⋮ An application of the Turán theorem to domination in graphs ⋮ On complexities of minus domination ⋮ Minus domination in small-degree graphs ⋮ Total minus domination in \(k\)-partite graphs ⋮ Minus domination number in cubic graph ⋮ On the Minus Domination Number of Graphs ⋮ Minus total domination in graphs ⋮ Dominating functions with integer values in graphs—a survey ⋮ Algorithms and Complexity of Signed, Minus, and Majority Domination ⋮ Signed and Minus Dominating Functions in Graphs ⋮ A note on graphs with large girth and small minus domination number ⋮ Minus domination in graphs ⋮ Real and integer domination in graphs ⋮ On Complexities of Minus Domination

Cites Work

• Contributions to the theory of domination, independence and irredundance in graphs
• Chordal graphs and upper irredundance, upper domination and independence
• Minus domination in graphs
• Dominating Sets in Chordal Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The algorithmic complexity of minus domination in graphs