Abstract
A setDof vertices of a graphG= (VG,EG) is a dominating set ofGif every vertexinVG−Dis adjacent to at least one vertex inD. The domination number (upper dominationnumber, respectively) ofG, denoted byγ(G) (Γ(G), respectively), is the cardinality ofa smallest (largest minimal, respectively) dominating set ofG. A subsetD⊆VGis calleda certified dominating set ofGifDis a dominating set ofGand every vertex inDhas eitherzero or at least two neighbors inVG−D. The cardinality of a smallest (largest minimal,respectively) certified dominating set ofGis called the certified (upper certified, respectively)domination number ofGand is denoted byγcer(G) (Γcer(G), respectively). In this paperrelations between domination, upper domination, certified domination and upper certifieddomination numbers of a graph are studied
Citations
-
1
CrossRef
-
0
Web of Science
-
2
Scopus
Authors (6)
Cite as
Full text
- Publication version
- Accepted or Published Version
- License
- open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
Opuscula Mathematica
no. 39,
pages 815 - 827,
ISSN: 1232-9274 - Language:
- English
- Publication year:
- 2019
- Bibliographic description:
- Dettlaff M., Lemańska M., Topp J., Miotk M., Ziemann R., Żyliński P.: Graphs with equal domination and certified domination numbers// Opuscula Mathematica -Vol. 39,iss. 6 (2019), s.815-827
- DOI:
- Digital Object Identifier (open in new tab) 10.7494/opmath.2019.39.6.815
- Bibliography: test
-
- 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. open in new tab
- 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. open in new tab
- M. Fischermann, Block graphs with unique minimum dominating sets, Discrete Math. 240 (2001), 247-251. open in new tab
- R. Frucht, F. Harary, On the corona of two graphs, Aequ. Math. 4 (1970), 322-324. open in new tab
- 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. open in new tab
- T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998. open in new tab
- M.A. Henning, A. Yeo, Total Domination in Graphs, Springer-Verlag, New York, 2013. Magda Dettlaff magda.dettlaff1@pg.edu.pl open in new tab
- Verified by:
- Gdańsk University of Technology
seen 93 times
Recommended for you
Total Domination Versus Domination in Cubic Graphs
- J. Cyman,
- M. Dettlaff,
- M. A. Henning
- + 2 authors