COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS

DOI10.1142/S1793830912500450zbMath1251.05127MaRDI QIDQ3166754

No author found.

Publication date: 15 October 2012

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830912500450

zbMATH Keywords

NP-complete; domination; total domination; \(k\)-tuple total domination; minus total domination; signed total domination

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

The cyclic rank completion problem with general blocks, An efficient algorithm for distance total domination in block graphs, k-Efficient domination: Algorithmic perspective, On the algorithmic complexity of \(k\)-tuple total domination, Algorithms and Complexity of Signed, Minus, and Majority Domination

Cites Work

• \(k\)-tuple total domination in graphs
• Domination in convex and chordal bipartite graphs
• Remarks on the minus (signed) total domination in graphs
• On the complexity of signed and minus total domination in graphs
• A survey of selected recent results on total domination in graphs
• Upper bounds on the upper signed total domination number of graphs
• Classes of bipartite graphs related to chordal graphs
• Signed total domination in graphs.
• Doubly lexical ordering of dense 0--1 matrices
• Incidence matrices and interval graphs
• Upper minus total domination in small-degree regular graphs
• Total minus domination in \(k\)-partite graphs
• Signed Total Domination Nnumber of a Graph
• Three Partition Refinement Algorithms
• Perfect Elimination and Chordal Bipartite Graphs
• Dually Chordal Graphs