- Tytuł:
- Dominating Vertex Covers: The Vertex-Edge Domination Problem
- Autorzy:
-
Klostermeyer, William F.
Messinger, Margaret-Ellen
Yeo, Anders - Powiązania:
- https://bibliotekanauki.pl/articles/32083812.pdf
- Data publikacji:
- 2021-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
cubic graph
dominating set
vertex cover
vertex-edge dominating set - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 123-132
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł