Efficient Domination in Graphs

Teresa W. Haynes, Stephen T. Hedetniemi, Michael A. Henning

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review


In this chapter, we consider the concept of efficient domination, that is, the concept of dominating every vertex exactly once. An efficient dominating set S ⊆ V in a graph G = (V, E) is a dominating set with the additional property that the closed neighborhood N[v] of every vertex v ∈ V contains exactly one vertex in S. It should be noted at the outset that not every graph has an efficient dominating set, the cycles C4 and C5 being two small examples. Thus, the study of efficient domination in graphs focuses primarily on families of graphs each member of which has an efficient dominating set, and then algorithms for finding such sets, or on families of graphs for which it can be determined in polynomial time which members do and do not have efficient dominating sets.

Original languageEnglish
Title of host publicationSpringer Monographs in Mathematics
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages31
Publication statusPublished - 2023

Publication series

NameSpringer Monographs in Mathematics
ISSN (Print)1439-7382
ISSN (Electronic)2196-9922

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Efficient Domination in Graphs'. Together they form a unique fingerprint.

Cite this