Dominating Vertex Covers: The Vertex-Edge Domination Problem
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 t...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2021-02-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2175 |
| _version_ | 1797713236442742784 |
|---|---|
| author | Klostermeyer William F. Messinger Margaret-Ellen Yeo Anders |
| author_facet | Klostermeyer William F. Messinger Margaret-Ellen Yeo Anders |
| author_sort | Klostermeyer William F. |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T07:32:38Z |
| format | Article |
| id | doaj.art-ad8518856b0941458a7ab22bae1a30b1 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T07:32:38Z |
| publishDate | 2021-02-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-ad8518856b0941458a7ab22bae1a30b12023-09-02T21:42:53ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922021-02-0141112313210.7151/dmgt.2175dmgt.2175Dominating Vertex Covers: The Vertex-Edge Domination ProblemKlostermeyer William F.0Messinger Margaret-Ellen1Yeo Anders2School of Computing, University of North Florida, Jacksonville, FL32224USADepartment of Mathematics and Computer Science, Mount Allison University, Sackville, NB, CanadaDepartment of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark and Department of Mathematics, University of Johannesburg, Auckland Park, 2006South AfricaThe 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.https://doi.org/10.7151/dmgt.2175cubic graphdominating setvertex coververtex-edge dominating set05c69 |
| spellingShingle | Klostermeyer William F. Messinger Margaret-Ellen Yeo Anders Dominating Vertex Covers: The Vertex-Edge Domination Problem Discussiones Mathematicae Graph Theory cubic graph dominating set vertex cover vertex-edge dominating set 05c69 |
| title | Dominating Vertex Covers: The Vertex-Edge Domination Problem |
| title_full | Dominating Vertex Covers: The Vertex-Edge Domination Problem |
| title_fullStr | Dominating Vertex Covers: The Vertex-Edge Domination Problem |
| title_full_unstemmed | Dominating Vertex Covers: The Vertex-Edge Domination Problem |
| title_short | Dominating Vertex Covers: The Vertex-Edge Domination Problem |
| title_sort | dominating vertex covers the vertex edge domination problem |
| topic | cubic graph dominating set vertex cover vertex-edge dominating set 05c69 |
| url | https://doi.org/10.7151/dmgt.2175 |
| work_keys_str_mv | AT klostermeyerwilliamf dominatingvertexcoversthevertexedgedominationproblem AT messingermargaretellen dominatingvertexcoversthevertexedgedominationproblem AT yeoanders dominatingvertexcoversthevertexedgedominationproblem |