The algorithmic complexity of minus domination in graphs

DOI10.1016/0166-218X(95)00056-WMaRDI QIDQ1917346zbMATH OpenOpenAlexFDO

Authors Jean E. Dunbar, Stephen T. Hedetniemi, Alice A. McRae, Michael A. Henning, 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

algorithmminus dominating functionminus domination numberNP-completetreeweight

Mathematics Subject Classification ID

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

Recommendations

• Algorithmic aspect of minus domination on small-degree graphs
• On the complexity of signed and minus total domination in graphs
• Algorithmic aspects of minus total k-subdomination in graphs
• On minus domination in graphs
• The algorithmic complexity of domination digraphs
• scientific article; zbMATH DE number 2080250
• Efficient minus and signed domination in graphs
• scientific article; zbMATH DE number 825134
• A note on the complexity of minimum dominating set
• Minus domination in graphs

Cites work

• Chordal graphs and upper irredundance, upper domination and independence
• Contributions to the theory of domination, independence and irredundance in graphs
• Dominating Sets in Chordal Graphs
• scientific article; zbMATH DE number 4089545 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 870426 (Why is no real title available?)
• Minus domination in graphs

Cited in

(34)

• A note on graphs with large girth and small minus domination number
• Minus domination in graphs
• Real and integer domination 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.
• On complexities of minus domination
• Minus domination in regular graphs
• The complexity of the vertex-minor problem
• The algorithmic complexity of the minus clique-transversal problem
• Upper minus total domination in small-degree regular graphs
• A note on the complexity of minimum dominating set
• Total minus domination in \(k\)-partite graphs
• On complexities of minus domination
• Minus total domination in graphs.
• Algorithmic aspect of minus domination on small-degree graphs
• On the Minus Domination Number of Graphs
• Algorithms and complexity of signed, minus, and majority domination
• Signed and minus dominating functions in graphs
• Algorithmic aspects of minus total k-subdomination in graphs
• scientific article; zbMATH DE number 1262784 (Why is no real title available?)
• scientific article; zbMATH DE number 2080250 (Why is no real title available?)
• scientific article; zbMATH DE number 2104725 (Why is no real title available?)
• On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
• The minus total k-domination numbers in graphs
• Dominating functions with integer values in graphs—a survey
• Minus domination in small-degree graphs
• Minus domination number in cubic graph
• k-minimal minus domination and self-stabilization
• Structural parameterization of minus domination
• Structural parameterization of minus domination
• Upper minus domination in a claw-free cubic graph
• Variations of \(Y\)-dominating functions on graphs
• An application of the Turán theorem to domination in graphs

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

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