DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

W.F. Klostermeyer, M.E. Messinger, A. Yeo

Title:

Dominating vertex covers: a searchlight problem

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-01-04, Revised: 2018-08-25, Accepted: 2018-08-25, https://doi.org/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}\leq 9n/26$. We also show that it is $NP$-hard to decide if $\ed{G}=\gamma(G)$ for bipartite graph $G$.

Keywords:

cubic graph, dominating set, vertex cover, vertex-edge dominating set

PDF
Close