Dominating vortex covers: The vertex-edge domination problem

William F. Klostermeyer, Margaret Ellen Messinger, Anders Yeo

Research output: Contribution to journalJournal articleResearchpeer-review

1 Downloads (Pure)

Abstract

The vertex-edge domination number of a graph, gamma(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, gamma(ve) (G)
Original languageEnglish
JournalDiscussiones Mathematicae. Graph Theory
Volume41
Issue number1
Pages (from-to)123-132
ISSN1234-3099
DOIs
Publication statusPublished - 2021

Keywords

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

Fingerprint Dive into the research topics of 'Dominating vortex covers: The vertex-edge domination problem'. Together they form a unique fingerprint.

Cite this