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.

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.
  • Received: 2018-12-07.
  • Revised: 2019-07-26.
  • Accepted: 2019-08-01.
  • Published online: 2019-11-22.
Opuscula Mathematica - cover

Cite this article as:
Magda Dettlaff, Magdalena Lemańska, Mateusz Miotk, Jerzy Topp, Radosław Ziemann, Paweł Żyliński, Graphs with equal domination and certified domination numbers, Opuscula Math. 39, no. 6 (2019), 815-827, https://doi.org/10.7494/OpMath.2019.39.6.815

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.