Graphs with equal domination and certified domination numbers

• Autorzy: Dettlaff Magda , Lemańska Magdalena , Miotk Mateusz , Topp Jerzy , Ziemann Radosław , Żyliński Paweł

Identyfikatory

DOI

10.7494/OpMath.2019.39.6.815

• Języki publikacji: EN

Abstrakty

EN

A set D of vertices of a graph G = (VG, EG) 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 G, denoted by [formula], 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 [formula]), respectively). In this paper relations between domination, upper domination, certified domination and upper certified domination numbers of a graph are studied.

Słowa kluczowe

EN

domination; certified domination

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2019
• Tom: Vol. 39, no. 6
• Strony: 815--827
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Dettlaff Magda

• Gdańsk University of Technology Gabriela Narutowicza 11/12 80-233 Gdańsk, Poland

autor

Lemańska Magdalena

• Gdańsk University of Technology Gabriela Narutowicza 11/12 80-233 Gdańsk, Poland

autor

Miotk Mateusz

• University of Gdańsk Wita Stwosza 57 80-308 Gdańsk, Poland

autor

Topp Jerzy

• University of Gdańsk Wita Stwosza 57 80-308 Gdańsk, Poland

autor

Ziemann Radosław

• University of Gdańsk Wita Stwosza 57 80-308 Gdańsk, Poland

autor

Żyliński Paweł

• University of Gdańsk Wita Stwosza 57 80-308 Gdańsk, Poland

Bibliografia

• [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.
• [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. Rail, 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.