Authors:
W.F. Klostermeyer, M.E. Messinger, A. Yeo
Title:
Dominating vertex covers: a searchlight problem
Source:
Discussiones Mathematicae Graph Theory
Received 04.01.2018, Revised 25.08.2018, Accepted 25.08.2018, doi: 10.7151/dmgt.2175

Abstract:
The vertex-edge domination number of a graph, \ed{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, \ed{G}≤ 9n/26. We also show that it is NP-hard to decide if \ed{G}=γ(G) for bipartite graph G.
Keywords:
cubic graph, dominating set, vertex cover, vertex-edge dominating set

Links:
PDF