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: |