Dominating vertex covers: the vertex-edge domination problem (Q2214311)

A variant of domination, namely, vertex-edge domination in which a set of vertices dominating the edges is studied. The vertex-edge domination number of a graph \(G\), \(\gamma_{\mathrm{ve}}(G)\), is defined to be the cardinality of a smallest set \(D\) such that there exists a vertex cover \(C\) of \(G\) such that each vertex in \(C\) is dominated by a vertex in \(D\). Upper bounds of the vertex-edge domination number for trees and non-trivial connected graphs and connected \(C_5\)-free graphs are known. In the paper under review, the authors provide an upper bound for cubic graphs as \(\frac{9n}{26}\), where \(n\) is order of graph \(G\). They also prove that it is NP-hard to decide if \(\gamma_{ve}(G)=\gamma(G)\) for bipartite graph \(G\).