Opuscula Math. 39, no. 6 (2019), 815-827
https://doi.org/10.7494/OpMath.2019.39.6.815

Opuscula Mathematica

# Graphs with equal domination and certified domination numbers

Magda Dettlaff
Magdalena Lemańska
Mateusz Miotk
Jerzy Topp
Paweł Żyliński

Abstract. A set $$D$$ of vertices of a graph $$G=(V_G,E_G)$$ is a dominating set of $$G$$ if every vertex in $$V_G-D$$ is adjacent to at least one vertex in $$D$$. The domination number (upper domination number, respectively) of $$G$$, denoted by $$\gamma(G)$$ ($$\Gamma(G)$$, respectively), is the cardinality of a smallest (largest minimal, respectively) dominating set of $$G$$. A subset $$D\subseteq V_G$$ 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 $$V_G-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 $$\gamma_{\rm cer}(G)$$ ($$\Gamma_{\rm cer}(G)$$, respectively). In this paper relations between domination, upper domination, certified domination and upper certified domination numbers of a graph are studied.

Keywords: domination, certified domination.

Mathematics Subject Classification: 05C69.

Full text (pdf)

1. G.A. Cheston, G. Fricke, Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance, Discrete Appl. Math. 55 (1994), 241-258.
2. M. Dettlaff, M. Lemańska, J. Topp, R. Ziemann, P. Żyliński, Certified domination, AKCE Int. J. Graphs Comb., to appear, doi:10.1016/j.akcej.2018.09.004. https://doi.org/10.1016/j.akcej.2018.09.004
3. M. Fischermann, Block graphs with unique minimum dominating sets, Discrete Math. 240 (2001), 247-251.
4. R. Frucht, F. Harary, On the corona of two graphs, Aequ. Math. 4 (1970), 322-324.
5. G. Gunther, B. Hartnell, L.R. Markus, D. Rall, Graphs with unique minimum dominating sets, Congr. Numer. 101 (1994), 55-63.
6. T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
7. T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
8. M.A. Henning, A. Yeo, Total Domination in Graphs, Springer-Verlag, New York, 2013.
• Communicated by Dalibor Fronček.
• Revised: 2019-07-26.
• Accepted: 2019-08-01.
• Published online: 2019-11-22.