Dominating vertex covers: the vertex-edge domination problem (Q2214311)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Dominating vertex covers: the vertex-edge domination problem |
scientific article |
Statements
Dominating vertex covers: the vertex-edge domination problem (English)
0 references
8 December 2020
0 references
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\).
0 references
cubic graphs
0 references
dominating set
0 references
vertex cover
0 references
vertex-edge dominating set
0 references