No Detail Found!

On a class of graphs with equal domination and certified domination numbers

Author(s)
Mateusz Miotk Institute of Informatics, University of Gda n ́sk,Wita Stwosza 57, 80-308 Gda n ́sk,Poland
Abstract
A graph G is called a DD2-graph if its vertex set VG can be partitioned into a dominating set D and a 2-dominating set VG - D. The domination number, ? (G), is the minimum cardinality of a dominating set. The certified domination number, ? cer(G), is the minimum size of a dominating set D such that every vertex in D has either zero or at least two neighbors in VG - D. In this paper, the minimal DD2-graphs G for which ? (G) = ? cer(G) are characterized, and it is shown that they are the cycle C4, the stars K1,n (n = 2), and the subdivisions of the connected corona graphs cor(K1) and cor(K2). A characterization is also provided for bipartite graphs in which the smaller partite set serves simultaneously as a ? -set and a ? cer-set. A conjecture concerning trees and several open problems are presented in conclusion.
Publication Details
Page(s) 29-34
Published Journal: Discrete Mathematics Letters, Volume: 16, Issue: 0, Year: 2025

Request the full text from PASTIC

Keywords
DD2-graph, dominating set, bipartite graph, certified domination, minimal DD2-graph
References
Chartrand G.,Lesniak L.,Zhang P. .2016 .. Graphs & Digraphs, 6th Edition, : .
Dettlaf M.,M. M.,Topp J.,Ziemann R.,P. R. .2019 .Z˙yli n´ski, Graphs with equal domination and certified domination numbers. , 39 : 815-827.
Dettlaf M.,M. M.,Ziemann R.,P. R. .2019 .Z˙ ylin´ ski, Certified domination. AKCE Int. J. Graphs Comb, 16 : 198-205.
Henning M. A.,Rall D. F. .2013 .On graphs with disjoint dominating and 2-dominating sets. Discuss. Math. Graph Theory, 33 : 139-146.
Lingas A.,Miotk M.,Topp J.,P. J. .2020 .Z˙ ylin´ ski, Graphs with equal domination and covering numbers. J. Comb. Optim, 39 : 55-71.
Miotk M.,Topp J.,P. J. .2020 .Z˙yli n´ski, Disjoint dominating and 2-dominating sets in graphs. Discrete Optim, 35 : 100553.
Wu Y.,Yu Q. .2012 .A characterization of graphs with equal domination number and vertex cover number. Bull. Malay. Math. Sci. Soc, 35 : 803-806.
0

Citations

0

Downloads

24

Views