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.
Mots-clés : 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 = {https://geodesic-test.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  - https://geodesic-test.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 https://geodesic-test.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. https://geodesic-test.mathdoc.fr/item/DMGT_2021_41_1_a7/

[1] R. Boutrig, M. Chellali, T.W. Haynes and S.T. Hedetniemi, Vertex-edge domination in graphs, Aequationes Math. 90 (2016) 355–366. doi: 10.1007/s00010-015-0354-2

[2] D. Dereniowski, H. Ono, I. Suzuki, Ł. Wrona, M. Yamashita and P. Żylinski, The searchlight problem for road networks, Theoret. Comput. Sci. 591 (2015) 28–59. doi: 10.1016/j.tcs.2015.04.026

[3] M.A. Henning and A. Yeo, Transversals in 4-uniform hypergraphs, Electron. J. Combin. 23 (2016) #P3.50.

[4] W.F. Klostermeyer and C.M. Mynhardt, Edge protection in graphs, Australas. J. Combin. 45 (2009) 235–250.

[5] W.F. Klostermeyer and C.M. Mynhardt, Protecting a graph with mobile guards, Appl. Anal. Discrete Math. 10 (2016) 1–29. doi: 10.2298/AADM151109021K

[6] A.V. Kostochka and C. Stocker, A new bound on the domination number of connected cubic graphs, Sib. Èlektron. Mat. Izv. 6 (2009) 465–504.

[7] B. Krishnakumari, Y.B. Venkatakrishnan and M. Krzywkowski, Bounds on the vertex-edge domination number of a tree, C.R. Math. 352 (2014) 363–366. doi: 10.1016/j.crma.2014.03.017

[8] J.R. Lewis, Vertex-Edge and Edge-Vertex Domination in Graphs, Ph.D. Thesis (Clemson University, Clemson, 2007).

[9] J.R. Lewis, S.T. Hedetniemi, T.W. Haynes and G.H. Fricke, Vertex-edge domination, Util. Math. 81 (2010) 193–213.

[10] J.W. Peters, Theoretical and Algorithmic Results on Domination and Connectivity, Ph.D. Thesis (Clemson University, Clemson, 1986).

[11] Y.B. Venkatakrishnan, C. Natarajan and G. Sathiamoorthy, Vertex-edge and connected domination numbers of a tree, Int. J. Pure Appl. Math. 119 (2018) 103–111.

[12] W.C.K. Yen and C.Y. Tang, An optimal algorithm for solving the searchlight guarding problem on weight two-terminal series-parallel graphs, Acta Inform. 36 (1999) 143–172. doi: 10.1007/s002360050156