Geodesic
Dominating Vertex Covers: The Vertex-Edge Domination Problem
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 123-132

Voir la notice de l'article provenant de la source Library of Science

The 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 NP-hard to decide if γve(G) = γ(G) for bipartite graph G.
Keywords: cubic graph, dominating set, vertex cover, vertex-edge dominating set 
@article{DMGT_2021_41_1_a7,
     author = {Klostermeyer, William F. and Messinger, Margaret-Ellen and Yeo, Anders},
     title = {Dominating {Vertex} {Covers:} {The} {Vertex-Edge} {Domination} {Problem}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {123--132},
     publisher = {mathdoc},
     volume = {41},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a7/}
}
TY  - JOUR
AU  - Klostermeyer, William F.
AU  - Messinger, Margaret-Ellen
AU  - Yeo, Anders
TI  - Dominating Vertex Covers: The Vertex-Edge Domination Problem
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 123
EP  - 132
VL  - 41
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a7/
LA  - en
ID  - DMGT_2021_41_1_a7
ER  - 
%0 Journal Article
%A Klostermeyer, William F.
%A Messinger, Margaret-Ellen
%A Yeo, Anders
%T Dominating Vertex Covers: The Vertex-Edge Domination Problem
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 123-132
%V 41
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a7/
%G en
%F DMGT_2021_41_1_a7
Klostermeyer, William F.; Messinger, Margaret-Ellen; Yeo, Anders. Dominating Vertex Covers: The Vertex-Edge Domination Problem. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 123-132. http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a7/