2017/10/05 by Dettlaff, Magda, Lemańska, Magdalena, Miotk, Mateusz +3
#05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1710.02059
A set D of vertices of a graph G is a dominating set of G if every vertex in VG-D is adjacent to at least one vertex in D. The domination number (upper domination number, respectively) of a graph G, denoted by γ(G) (Γ(G), respectively), is the cardinality of a smallest (largest minimal, respectively) dominating set of G. A subset D⊆ VG is called a certified dominating set of G if D is a dominating set of G and every vertex in D has either zero or at least two neighbors in VG-D. The cardinality of a~smallest (largest minimal, respectively) certified dominating set of G is called the certified upper certified, respectively domination number of G and is denoted by γ\rm cer(G) (Γ\rm cer(G), respectively). In this paper relations between domination, upper domination, certified domination and upper certified domination numbers of a graph are studied.