
doi: 10.7151/dmgt.2175
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\).
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), vertex-edge dominating set, 05c69, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), cubic graph, QA1-939, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), cubic graphs, dominating set, Mathematics, vertex cover
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), vertex-edge dominating set, 05c69, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), cubic graph, QA1-939, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), cubic graphs, dominating set, Mathematics, vertex cover
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
