Dominating vertex covers: the vertex-edge domination problem
2018; De Gruyter Open; Volume: 41; Issue: 1 Linguagem: Inglês
10.7151/dmgt.2175
ISSN2083-5892
AutoresWilliam F. Klostermeyer, M. Messinger, Anders Yeo,
Tópico(s)Optimization and Search Problems
ResumoThe vertex-edge domination number of a graph, γ 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. This is motivated by the problem of determining how many guards are needed in a graph so that a searchlight can be shone down each edge by a guard either incident to that edge or at most distance one from a vertex incident to the edge.Our main result is that for any cubic graph G with n vertices, γ ve (G) ≤ 9n/26.We also show that it is N P -hard to decide if γ ve (G) = γ(G) for bipartite graph G.
Referência(s)