
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\).
cubic graph, cubic graphs, dominating set, 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.), QA1-939, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Mathematics
cubic graph, cubic graphs, dominating set, 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.), QA1-939, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Mathematics
| 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 |
