On the complexity of signed and minus total domination in graphs

DOI10.1016/J.IPL.2009.08.002MaRDI QIDQ990954zbMATHOpenAlexFDO

Authors Chuan-Min Lee

Publication date 1 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.08.002

zbMATH Keywords

graph algorithmschordal bipartite graphsdoubly chordal graphsminus total dominating functionssigned total dominating functions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Signed and minus total domination on subclasses of bipartite graphs.
• Total dominating functions on subclasses of chordal graphs
• scientific article; zbMATH DE number 2080250
• Complexity of certain functional variants of total domination in chordal bipartite graphs
• Efficient minus and signed domination in graphs

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 2104725 (Why is no real title available?)
• A survey of selected recent results on total domination in graphs
• An upper bound on the restrained domination number of graphs.
• Characterizations of strongly chordal graphs
• Doubly chordal graphs, steiner trees, and connected domination
• Doubly lexical ordering of dense 0--1 matrices
• Dually Chordal Graphs
• Graph Classes: A Survey
• On the Algorithmic Complexity of Total Domination
• Remarks on the minus (signed) total domination in graphs
• Signed Total Domination Nnumber of a Graph
• Signed total domination in graphs.
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Three Partition Refinement Algorithms
• Total minus domination in \(k\)-partite graphs
• Triangulated graphs and the elimination process
• Upper bounds on the upper signed total domination number of graphs
• Upper minus total domination in small-degree regular graphs
• Variations of \(Y\)-dominating functions on graphs

Cited in

(12)

• Algorithms and complexity of signed, minus, and majority domination
• Efficient minus and signed domination in graphs
• Kernelization and Lower Bounds of the Signed Domination Problem
• The algorithmic complexity of minus domination in graphs
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• Total dominating functions on subclasses of chordal graphs
• Algorithms and Hardness for Signed Domination
• Complexity of certain functional variants of total domination in chordal bipartite graphs
• scientific article; zbMATH DE number 2080250 (Why is no real title available?)
• scientific article; zbMATH DE number 6269006 (Why is no real title available?)
• Signed and minus total domination on subclasses of bipartite graphs.
• Remarks on the complexity of signed \(k\)-independence on graphs.

This page was built for publication: On the complexity of signed and minus total domination in graphs

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