Total domination in block graphs
A set of vertices D is a total dominating set for a graph G if every vertex of G is adjacent with at least one vertex in D. Although the problem of determining the minimum cardinality of a total dominating set for an arbitrary graph is NP-complete, polynomial time algorithm are known for certain classes of graphs (e.g. trees, interval graphs). The paper contains an \(O(| V| +| E|)\) time algorithm which solves this problem for block graphs. In fact, the algorithm presented here deals with a more general problem which, for particular instances, gives solutions for both domination and total domination problems.
- R -Domination in Graphs
- A linear algorithm for the domination number of a series-parallel graph
- A linear algorithm for the domination number of a tree
- Covering, Packing and Generalized Perfection
- Dominating Sets in Chordal Graphs
- Domination in permutation graphs
- Domination, independent domination, and duality in strongly chordal graphs
- scientific article; zbMATH DE number 3910441 (Why is no real title available?)
- scientific article; zbMATH DE number 4055676 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- On the Algorithmic Complexity of Total Domination
- On the computational power of pushdown automata
- R-domination of block graphs
- The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
- The NP-completeness column: An ongoing guide
- Total domination in interval graphs
- Labeling algorithms for domination problems in sun-free chordal graphs
- On the computational complexity of upper total domination
- The bottleneck independent domination on the classes of bipartite graphs and block graphs.
- On total \(f\)-domination: polyhedral and algorithmic results
- Hardness results and approximation algorithm for total liar's domination in graphs
- The semitotal domination problem in block graphs
- Roman \(\{2\}\)-domination problem in graphs
- A linear-time algorithm for weighted paired-domination on block graphs
- Domination number of incidence graphs of block designs
- Power domination in block graphs
- Domination and irredundance in graphs with restricted blocks
- Total domination and transformation
- Total domination in circular-arc graphs
- scientific article; zbMATH DE number 4204394 (Why is no real title available?)
- scientific article; zbMATH DE number 5163125 (Why is no real title available?)
- scientific article; zbMATH DE number 3910441 (Why is no real title available?)
- On the Algorithmic Complexity of Total Domination
- scientific article; zbMATH DE number 4051684 (Why is no real title available?)
- On the algorithmic complexity of \(k\)-tuple total domination
- scientific article; zbMATH DE number 1161341 (Why is no real title available?)
- scientific article; zbMATH DE number 1416465 (Why is no real title available?)
- Total domination in interval graphs
- Total domination in interval graphs
- An efficient algorithm for distance total domination in block graphs
- \(k\)-power domination in block graphs
- Convexity of minimal total dominating functions in graphs
- Bibliography on domination in graphs and some basic definitions of domination parameters
This page was built for publication: Total domination in block graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124531)
