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
Radosław Ziemann
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.
- 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.
- 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
- M. Fischermann, Block graphs with unique minimum dominating sets, Discrete Math. 240 (2001), 247-251.
- R. Frucht, F. Harary, On the corona of two graphs, Aequ. Math. 4 (1970), 322-324.
- G. Gunther, B. Hartnell, L.R. Markus, D. Rall, Graphs with unique minimum dominating sets, Congr. Numer. 101 (1994), 55-63.
- T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
- T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
- M.A. Henning, A. Yeo, Total Domination in Graphs, Springer-Verlag, New York, 2013.
- Magda Dettlaff
https://orcid.org/0000-0002-7296-1893- Gdańsk University of Technology, Gabriela Narutowicza 11/12, 80-233 Gdańsk, Poland
- Magdalena Lemańska
- https://orcid.org/0000-0002-0924-9924
- Gdańsk University of Technology, Gabriela Narutowicza 11/12, 80-233 Gdańsk, Poland
- Mateusz Miotk
- https://orcid.org/0000-0003-2768-7861
- University of Gdańsk, Wita Stwosza 57, 80-308 Gdańsk, Poland
- Jerzy Topp
- https://orcid.org/0000-0002-8069-7850
- University of Gdańsk, Wita Stwosza 57, 80-308 Gdańsk, Poland
- Radosław Ziemann
- https://orcid.org/0000-0001-9659-0911
- University of Gdańsk, Wita Stwosza 57, 80-308 Gdańsk, Poland
- Paweł Żyliński
- https://orcid.org/0000-0001-6378-7742
- University of Gdańsk, Wita Stwosza 57, 80-308 Gdańsk, Poland
- Communicated by Dalibor Fronček.
- Received: 2018-12-07.
- Revised: 2019-07-26.
- Accepted: 2019-08-01.
- Published online: 2019-11-22.
