Total vertex-edge domination in graphs: Complexity and algorithms

DOI10.1142/S1793830922500318MaRDI QIDQ5057738zbMATH OpenOpenAlexFDO

Authors Nitisha Singhwal, Palagiri Venkata Subba Reddy

Publication date 19 December 2022

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

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

zbMATH Keywords

approximation ratiograph classeslinear programmingNP-completenesstree-convex bipartite graphsvertex-edge domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Total vertex-edge domination
• Total vertex-edge domination in trees
• Total outer connected vertex-edge domination
• Double vertex-edge domination in graphs: complexity and algorithms
• On the algorithmic complexity of double vertex-edge domination in graphs

Cites work

• A lower bound on the total vertex-edge domination number of a tree
• Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
• Algorithmic aspects of \(b\)-disjunctive domination in graphs
• Algorithmic aspects of semitotal domination in graphs
• Algorithms and Computation
• Captive domination in graphs
• Double vertex-edge domination
• Doubly connected bi-domination in graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Linear programming approach for various domination parameters
• Linear programming formulation for some generalized domination parameters
• On trees with domination number equal to edge-vertex Roman domination number
• On vertex-edge and independent vertex-edge domination
• Planar 3DM is NP-complete
• Quadruple Roman domination in graphs
• Reducibility among combinatorial problems
• Threshold graphs and related topics
• Total vertex-edge domination
• Two Hardness Results on Feedback Vertex Sets
• Vertex-edge domination in cubic graphs
• Vertex-edge domination in graphs

Cited in

(15)

• An \(O(| V|^*| E|)\) algorithm for finding immediate multiple-vertex dominators
• The complexity of total edge domination and some related results on trees
• Algorithmic aspects of upper edge domination
• Double vertex-edge domination in graphs: complexity and algorithms
• Dominating vertex covers: the vertex-edge domination problem
• The computational complexity of the edge-perfect graph and the totally balanced packing game recognition problems
• Total vertex-edge domination in trees
• On the algorithmic complexity of double vertex-edge domination in graphs
• Vertex-edge domination in graphs
• Vertex-edge domination in unit disk graphs
• Vertex-edge domination in unit disk graphs
• On \(k\)-vertex-edge domination of graph
• Edge-vertex domination of acyclic trapezoid graphs: algorithm and complexity
• Algorithmic aspects of total vertex-edge domination in graphs
• On total isolation in graphs

This page was built for publication: Total vertex-edge domination in graphs: Complexity and algorithms

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