TY - CHAP

T1 - Efficient Domination in Graphs

AU - Haynes, Teresa W.

AU - Hedetniemi, Stephen T.

AU - Henning, Michael A.

N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2023.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85159111609&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-09496-5_9

DO - 10.1007/978-3-031-09496-5_9

M3 - Chapter

AN - SCOPUS:85159111609

T3 - Springer Monographs in Mathematics

SP - 259

EP - 289

BT - Springer Monographs in Mathematics

PB - Springer Science and Business Media Deutschland GmbH

ER -